QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#216429#6634. Central Subsetsiddharthjoshi026WA 41ms3600kbC++231.3kb2023-10-15 18:14:172023-10-15 18:14:18

Judging History

你现在查看的是最新测评结果

  • [2023-10-15 18:14:18]
  • 评测
  • 测评结果:WA
  • 用时:41ms
  • 内存:3600kb
  • [2023-10-15 18:14:17]
  • 提交

answer

#include <bits/stdc++.h> 
using namespace std;
#define f first
#define s second
int main(){
	long long zz;
	cin>>zz;
	while(zz--){
		long long n,m;
		cin>>n>>m;
		vector<long long> adj[n];
		vector<bool> visited(n,0);
		vector<long long> depth(n,-1);
		set<long long> stt,poss;
		long double d = sqrtl(n);
    	long long bor = d;
   	    if(bor < d) bor++;
		for(long long i=0;i<m;i++){
		long long x,y;
		cin>>x>>y;
		x--;y--;
		adj[x].push_back(y);
		adj[y].push_back(x);
		}
		bool flag=1;
		while(flag){
		queue<int> q;
		stt.clear();
		poss.clear();
		int y=rand();
		y%=n;
		stt.insert(y);
		visited[y]=1;
		q.push(y);
		depth[y]=0;
		while(!q.empty()){
		while(!q.empty()){
			int v=q.front();
			q.pop();
			for(auto x:adj[v]){
				if(!visited[x]){
					q.push(x);
					visited[x]=1;
					depth[x]=1+depth[v];}
			}
		}
		for(int i=0;i<n;i++){
			if(depth[i]>=bor){
				visited[i]=0;
				depth[i]=-1;
			}
			if(depth[i]==bor-1){
				poss.insert(i);
				visited[i]=0;
			}
		}
		for(auto x:poss){
			if(!visited[x]){
				stt.insert(x);
				depth[x]=0;
				visited[x]=1;
				q.push(x);
				break;
			}
		}
		}
		if(stt.size()<=bor){
		cout<<stt.size()<<'\n';
		for(auto x:stt){
			cout<<1+x<<' ';
		}
		cout<<'\n';
		flag=0;}
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3600kb

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
3 
2
2 4 

result:

ok correct (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 41ms
memory: 3576kb

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:

1
2 
3
1 3 4 
3
3 6 9 
2
1 2 
2
1 2 
1
4 
2
1 2 
1
3 
1
3 
1
12 
5
4 8 12 16 20 
1
5 
3
4 7 8 
1
15 
1
2 
1
13 
3
1 3 4 
2
1 2 
1
9 
1
8 
1
4 
1
3 
1
13 
2
6 11 
1
2 
1
2 
3
1 3 5 
1
14 
1
3 
1
2 
1
3 
1
3 
1
13 
1
5 
1
4 
3
1 3 5 
3
2 4 5 
3
2 5 9 
1
10 
1
5 
4
1 4 7 10 
3
1 3 4 
1
11 
1
2 
1
1 
3
...

result:

wrong answer Condition failed: "getMaxBfsDist(n, subset) <= csqrtn" (test case 1)