QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#127081#6634. Central Subsetyy_zq#WA 16ms8856kbC++14889b2023-07-19 12:52:092023-07-19 12:53:44

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-19 12:53:44]
  • 评测
  • 测评结果：WA
  • 用时：16ms
  • 内存：8856kb
查看
  • [2023-07-19 12:52:09]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,j,k) for(int i=j;i<=k;++i) 
const int MAX = 2e5+111;
int vis[MAX];
vector <int> e[MAX];
int ans[MAX];
int cnt;
int sqrtn;
int dfs(int x){
	int len = 0;
	vis[x]=1;
	for(int nxt:e[x]){
		if(!vis[nxt]){
			len = max(len,dfs(nxt));
		}
	}
	++len;
	if(len==sqrtn){
		ans[++cnt] = x;
		return 0;
	}
	if(!cnt && x==1) ans[++cnt] = 1;
	return len;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		int n,m,x,y;
		cin>>n>>m;
		sqrtn = sqrt(n);
		if(n!=sqrtn*sqrtn) ++sqrtn;
		FOR(i,1,m){
			cin>>x>>y;
			e[x].push_back(y);
			e[y].push_back(x);
		}
		dfs(1);
		cout<<cnt<<endl;
		FOR(i,1,cnt) cout<<ans[i]<<' ';
		cout<<endl;
		cnt = 0;
		FOR(i,1,n) ans[i]=0,vis[i]=0,e[i].clear();
	}
	return 0;
}
/*
2
5 4
1 2
1 3
1 4
1 5
*/
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 8064kb

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:

2
3 1 
2
4 1

result:

ok correct (2 test cases)

Test #2:

score: 0
Accepted
time: 8ms
memory: 8332kb

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
12 8 4 
1
2 
1
3 
1
1 
1
1 
3
7 4 1 
1
1 
2
5 2 
2
12 4 
1
1 
4
16 11 6 1 
2
4 2 
1
3 
2
8 2 
1
1 
3
12 8 4 
1
2 
1
1 
2
4 2 
1
1 
2
3 1 
2
4 2 
2
5 2 
2
8 2 
1
1 
3
12 8 4 
1
2 
2
6 3 
1
2 
1
1 
4
17 12 7 2 
1
3 
2
5 2 
3
10 6 1 
1
1 
2
4 1 
1
3 
2
4 1 
3
10 9 2 
1
1 
3
9 5 1 
1
2 
2
4 1 
2
3 1 
...

result:

ok correct (10000 test cases)

Test #3:

score: -100
Wrong Answer
time: 16ms
memory: 8856kb

input:

100
2000 1999
529 528
885 884
1221 1222
375 374
245 244
758 757
711 710
1521 1522
1875 1874
749 750
823 822
1959 1958
1767 1766
155 154
631 632
825 824
1330 1331
457 456
1344 1343
1817 1818
413 414
582 583
1828 1827
1335 1336
654 655
162 161
1668 1667
1966 1967
1472 1471
1185 1184
518 517
1509 1510
...

output:

44
1956 1911 1866 1821 1776 1731 1686 1641 1596 1551 1506 1461 1416 1371 1326 1281 1236 1191 1146 1101 1056 1011 966 921 876 831 786 741 696 651 606 561 516 471 426 381 336 291 246 201 156 111 66 21 
1
1 
22
957 913 869 825 781 737 693 649 605 561 517 473 429 385 341 297 253 209 165 121 77 33 
5
106...

result:

wrong answer Condition failed: "getMaxBfsDist(n, subset) <= csqrtn" (test case 74)
English 繁體中文 简体中文

Server Time: 2024-12-05 10:21:39 | OpenSource Project