QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #127532 | #6634. Central Subset | shielder | WA | 34ms | 8176kb | C++20 | 1.5kb | 2023-07-19 19:24:01 | 2023-07-19 19:24:03 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
vector<int> e[N];
vector<int> ans;
int dis[N];
int n, m, k;
int x ,y;
bool vis[N];
void bfs(int x){
dis[x] = 0;
vis[x] = 1;
queue<int> q;
q.push(x);
while(!q.empty()){
int u = q.front();
q.pop();
for(auto y : e[u]){
if(vis[y]) continue;
vis[y] = 1;
dis[y] = dis[u] + 1;
q.push(y);
}
}
for(int i = 1;i <= n;i++){
if(dis[i]%(k+1) == 1){
ans.push_back(i);
}
}
return ;
}
int main(){
int tt;
cin >> tt;
while(tt--){
cin >> n >>m;
ans.clear();
for(int i = 1;i <= n;i++){
e[i].clear();
vis[i] = 0;
dis[i] = 0;
}
k = ceil(sqrt(n));
for(int i = 1;i <= m;i++){
cin >> x >> y;
e[x].push_back(y);
e[y].push_back(x);
}
bfs(1);
cout << ans.size() << "\n";
for(auto x : ans){
cout << x << " ";
}
cout << "\n";
}
return 0;
}
/*
10000
15 14
13 12
5 4
9 8
11 12
15 14
10 9
14 13
2 3
2 1
6 5
10 11
3 4
7 6
8 7
6 5
2 1
2 4
4 6
2 3
3 5
10 9
8 3
9 4
5 6
5 10
3 2
5 4
2 7
1 2
4 3
2 1
2 1
2 1
2 1
9 8
9 8
5 4
1 2
6 5
3 4
3 2
7 8
7 6
2 1
1 2
14 13
3 10
5 6
2 9
11 4
2 3
2 1
8 7
13 6
5 4
5 12
6 7
4 3
7 14
16 15
2 3
2 1
6 10
6 9
6 4
9 11
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 8176kb
input:
2 4 3 1 2 2 3 3 4 6 7 1 2 2 3 3 1 1 4 4 5 5 6 6 4
output:
1 2 3 2 3 4
result:
ok correct (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 34ms
memory: 8120kb
input:
10000 15 14 13 12 5 4 9 8 11 12 15 14 10 9 14 13 2 3 2 1 6 5 10 11 3 4 7 6 8 7 6 5 2 1 2 4 4 6 2 3 3 5 10 9 8 3 9 4 5 6 5 10 3 2 5 4 2 7 1 2 4 3 2 1 2 1 2 1 2 1 9 8 9 8 5 4 1 2 6 5 3 4 3 2 7 8 7 6 2 1 1 2 14 13 3 10 5 6 2 9 11 4 2 3 2 1 8 7 13 6 5 4 5 12 6 7 4 3 7 14 16 15 2 3 2 1 6 10 6 9 6 4 9 11 ...
output:
3 2 7 12 1 2 1 2 1 2 1 2 2 2 6 1 2 3 2 7 13 3 2 11 12 1 2 4 2 8 14 20 2 2 8 1 2 3 2 14 15 1 2 3 2 7 12 1 2 1 2 1 2 1 2 1 2 2 2 8 3 2 7 13 4 2 15 16 17 1 2 3 2 7 12 1 2 3 2 7 14 1 2 1 2 4 2 8 14 20 1 2 3 2 7 13 4 2 12 13 14 1 2 2 2 6 1 2 3 2 7 12 3 2 11 12 1 2 ...
result:
wrong answer Integer 4 violates the range [1, 3] (test case 194)