QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #127451 | #6634. Central Subset | shielder | WA | 22ms | 15712kb | C++20 | 2.4kb | 2023-07-19 18:08:29 | 2023-07-19 18:08:32 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
vector<int> v[N], e[N];
int a[N], b[N];
int dis[N], dep[N];
bool vis[N];
vector<int> ans;
int n, m, k;
int x, y;
int ed, mxdis, st;int _tmp;
// void bfs(int st){
// mxdis= 0;
// queue<int> q;
// q.push(st);
// dis[st] = 0;
// vis[st] = 1;
// while(!q.empty()){
// int x = q.front();
// q.pop();
// for(auto y : v[x]){
// if(vis[y]) continue;
// vis[y] = 1;
// e[x].push_back(y);
// dis[y] = dis[x] + 1;
// q.push(y);
// }
// }
// }
void _dfs(int x){
if(vis[x]) return;
vis[x]=1;
for(auto y:v[x]){
if(vis[y]) continue;
_dfs(y);
dis[x]=max(dis[x],dis[y]+1);
}
if(dis[x]>=k){ans.push_back(x);dis[x]=-1;}
}
// int dfs(int x){
// if(e[x].size() == 0){
// dep[x] = 0;
// return 0 ;
// }
// int mx = 0;
// for(auto y : e[x]) mx = max(dfs(y), mx);
// ++mx;
// dep[x]=mx;
// if((mx == k || mx %(2*k)==0)){
// ans.push_back(x);
// }
// return mx;
// }
// int dfs_1(int x){
// if(e[x].size() == 0){
// dep[x] = 0;
// return 0 ;
// }
// int mx=0;
// for(auto y : e[x]) mx = max(dfs_1(y), mx);
// ++mx;
// return mx;
// }
int main(){
int tt;
cin >> tt;
while(tt--){
cin >> n >> m;
ans.clear();
k = ceil(sqrt(n));
dis[1]=-1;
for(int i = 1;i <= m;i++){
cin >>x >> y;
v[x].emplace_back(y);
v[y].emplace_back(x);
}
// if(n == 1){
// cout << "1\n1\n";
// continue;
// }
// st=1;
// bfs(st);//cout << "-----------\n";
// _tmp=dfs_1(st);
// dfs(st);
// ans.push_back(st);
_dfs(1);
if(ans.size() > k) cout << "-1\n";
else{
if(ans.size()==0) ans.push_back(1);
cout <<ans.size() << "\n";
for(auto x : ans) cout <<x << " ";
cout << "\n";
}
for(int i = 1;i <= n;i++){
v[i].clear();
e[i].clear();
vis[i] = 0;
}
}
return 0;
}
/*
16 15
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 12888kb
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 1 1
result:
ok correct (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 22ms
memory: 15712kb
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 11 6 1 1 2 1 2 1 1 1 1 2 7 3 1 1 3 6 5 2 3 10 6 2 1 2 4 15 11 5 1 -1 1 2 3 15 10 2 3 5 3 2 3 12 7 2 2 3 2 1 1 3 6 8 2 1 2 2 4 3 1 2 2 6 2 3 14 8 3 3 6 4 1 4 12 11 7 2 2 3 1 4 16 7 5 2 1 3 2 8 2 4 16 11 6 1 -1 3 7 6 2 3 11 6 2 2 3 2 1 3 2 7 3 2 4 2 5 12 14 9 4 1 ...
result:
wrong answer Integer -1 violates the range [1, 3] (test case 12)