QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#381460#3067. Justified JungleI_Love_Sonechka#AC ✓5641ms70992kbC++141.6kb2024-04-07 18:05:562024-04-07 18:05:56

Judging History

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

  • [2024-04-07 18:05:56]
  • 评测
  • 测评结果:AC
  • 用时:5641ms
  • 内存:70992kb
  • [2024-04-07 18:05:56]
  • 提交

answer

#include <bits/stdc++.h>
#include <math.h>
			
using namespace std;

// c++ short types
#define Int long long
#define vt vector

inline int read() {
	bool minus = false;
	int result = 0;
	char ch = getchar();
	while(true) {
		if(ch == '-') break;
		if(ch >= '0' && ch <= '9') break;
		ch = getchar();
	}
	if(ch == '-') minus = true;
	else result = ch - '0';
	while(true) {
		ch = getchar();
		if(ch < '0' || ch > '9') break;
		result = result * 10 + (ch-'0');
	}
	return (minus ? -result : result);
}

bool debug = false;

void solver() {
	int n; cin >> n;
	if(debug) {
		n = 1e6;
	}
	vt<vt<int>> g(n);
	for(int i = 1; i < n; ++i) {
		int a, b; 
		if(debug) {
			a = rand() % i + 1, b = i + 1;
		} else {
			a = read(), b = read();
		}
		g[--a].push_back(--b);
		g[b].push_back(a);
	}
	vt<int> order, parent(n, -1);
	queue<int> q;
	q.push(0);
	while(not q.empty()) {
		int u = q.front(); q.pop(); order.push_back(u);
		for(int to: g[u]) if(to ^ parent[u]) {
			q.push(to);
			parent[to] = u;
		}
	}
	reverse(order.begin(), order.end());
	vt<int> sz(n, 0);
	auto check = [&](int x) -> bool {
		for(int i: order) {
			sz[i] = 1;
			for(int from: g[i]) if(from ^ parent[i]) {
				sz[i] += sz[from];
			}
			if(sz[i] >= x) {
				if(sz[i] != x) {
					return 0;
				}
				sz[i] = 0;
			}
		}
		return sz[0] == 0;
	};
	for(int d = 1; d <= n-1; ++d) {
		if(n % (d+1) == 0 && check(n/(d+1))) {
			cout << d << " ";
		}
	}
}

int main()
{
//	ios::sync_with_stdio(false);
	//cin.tie(nullptr);
	int tt = 1;
	for(int t = 0; t < tt; ++t) {
    solver();
	}
	return 0;
}

詳細信息

Test #1:

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

input:

8
1 2
2 3
1 4
4 5
6 7
8 3
7 3

output:

1 3 7 

result:

ok single line: '1 3 7 '

Test #2:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

96
73 27
3 59
32 76
74 17
38 8
93 46
11 23
9 68
73 59
3 32
32 74
74 8
8 93
46 11
11 9
7 71
92 78
29 35
34 51
81 36
65 79
2 58
6 40
7 92
78 35
35 51
34 36
81 65
65 2
2 6
39 21
25 24
77 94
42 75
39 24
24 77
94 75
54 64
63 88
91 67
85 31
64 88
63 67
91 85
42 91
32 7
92 85
47 49
90 14
62 5
89 96
69 50
4...

output:

1 2 5 11 23 47 95 

result:

ok single line: '1 2 5 11 23 47 95 '

Test #3:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

90
73 27
73 3
59 32
32 76
74 17
74 38
8 19
8 46
11 23
23 9
27 32
76 38
17 19
19 23
68 7
68 71
7 86
7 78
29 35
29 34
29 51
35 81
36 65
36 79
65 2
79 58
86 35
29 2
6 40
40 39
21 25
21 24
77 61
77 42
75 54
75 64
63 88
88 53
6 21
25 61
77 54
64 53
73 68
35 6
67 85
85 31
47 49
47 90
14 62
14 5
89 57
57 6...

output:

1 5 89 

result:

ok single line: '1 5 89 '

Test #4:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

84
73 27
27 3
73 59
32 76
76 74
74 17
38 8
38 19
19 46
11 23
11 9
23 68
7 71
7 66
66 78
29 35
35 34
35 51
81 36
36 65
65 79
27 76
32 46
19 23
68 78
66 34
35 36
2 58
2 6
2 40
39 21
39 25
25 24
77 61
77 42
61 75
54 64
64 63
64 41
53 67
53 80
80 31
47 49
49 1
1 14
62 5
62 20
62 57
58 25
25 75
61 64
63 ...

output:

2 20 83 

result:

ok single line: '2 20 83 '

Test #5:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

72
18 27
3 59
32 30
18 3
3 30
13 17
38 8
19 46
17 38
8 46
11 23
23 9
68 7
7 71
9 7
27 8
46 9
66 60
66 29
35 34
35 51
60 51
33 36
65 55
2 58
33 55
55 2
6 40
39 21
25 24
40 21
21 24
29 33
55 40
56 61
56 42
26 54
26 64
42 26
63 41
53 67
52 31
41 53
67 52
47 49
47 1
14 62
14 5
49 14
61 41
67 5
20 57
57 ...

output:

1 3 5 11 71 

result:

ok single line: '1 3 5 11 71 '

Test #6:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

60
18 27
18 3
3 59
32 30
30 13
32 17
38 8
8 19
8 46
18 13
30 19
11 23
11 9
22 7
22 44
45 60
60 29
35 34
35 51
23 22
22 60
45 35
33 36
15 55
2 58
6 40
39 21
25 24
33 15
55 58
58 6
6 21
21 25
56 37
37 42
26 54
54 10
37 10
28 41
28 53
4 52
52 31
28 4
54 28
47 49
47 1
14 43
43 5
20 57
57 16
50 48
50 12
...

output:

4 59 

result:

ok single line: '4 59 '

Test #7:

score: 0
Accepted
time: 6ms
memory: 4044kb

input:

9240
2941 6908
6908 1183
2941 2275
1318 846
1318 2744
1318 4385
4039 2376
4039 5892
4039 1638
5186 6783
5186 626
6783 6554
1580 9169
1580 840
9169 2565
8320 6325
6325 4647
8320 3130
590 1481
590 4417
590 5936
2 2673
2673 7664
2 3173
3817 5863
5863 7946
7946 739
3016 2330
3016 3466
2330 523
7757 6565...

output:

1 2 4 5 6 9 10 13 14 20 21 29 32 34 41 54 65 69 76 104 109 153 164 209 230 329 384 461 769 1154 2309 9239 

result:

ok single line: '1 2 4 5 6 9 10 13 14 20 21 29 ...329 384 461 769 1154 2309 9239 '

Test #8:

score: 0
Accepted
time: 2ms
memory: 3880kb

input:

7560
2941 6908
2941 1183
2275 1318
2275 846
2744 4385
4385 4039
2376 5892
5892 1638
5186 6783
5186 626
6554 1580
1580 3472
840 2565
840 6907
6325 4647
4647 3130
590 1481
1481 4417
5936 2
5936 2673
6079 3173
6079 3817
5863 2802
5863 739
3016 2330
3016 3466
523 1293
523 6565
1111 1929
1929 5069
1183 2...

output:

1 2 3 7 7559 

result:

ok single line: '1 2 3 7 7559 '

Test #9:

score: 0
Accepted
time: 4ms
memory: 4072kb

input:

9360
2941 6908
2941 1183
2275 1318
2275 846
2744 4385
4385 4039
2376 5892
5892 1638
5186 6783
5186 626
6554 1580
6554 9169
840 2565
840 8320
6325 4647
6325 3130
590 1481
1481 4417
5936 2
5936 2673
6908 846
1318 2744
4385 2376
2376 5186
626 1580
1580 8320
8320 4647
3130 1481
4417 5936
7664 3173
3817 ...

output:

1 2 3 5 7 11 12 23 25 38 51 77 103 155 311 9359 

result:

ok single line: '1 2 3 5 7 11 12 23 25 38 51 77 103 155 311 9359 '

Test #10:

score: 0
Accepted
time: 3ms
memory: 4196kb

input:

8400
2941 6908
6908 1183
6908 2275
1318 846
1318 2744
1318 4385
4039 2376
4039 5892
4039 1638
5186 6783
6783 626
626 6554
1580 3472
3472 840
1580 2565
8320 6325
6325 4647
4647 3130
1183 4385
2744 1638
5892 6554
6554 3472
840 8320
590 1481
590 4417
5936 2
5936 2673
7664 3173
7664 3817
5863 7946
7946 ...

output:

1 3 4 6 9 13 24 34 49 69 174 349 8399 

result:

ok single line: '1 3 4 6 9 13 24 34 49 69 174 349 8399 '

Test #11:

score: 0
Accepted
time: 2ms
memory: 3920kb

input:

7920
2941 6908
1183 2275
1318 846
2744 4385
4039 2376
5892 1638
5186 6783
626 6554
1580 3472
840 2565
6907 6325
4647 3130
590 1481
4417 5936
2 2673
7664 3173
3817 5863
2802 739
3016 2330
3466 523
7757 6565
1111 1929
5069 1557
6960 7355
1047 6788
1579 1120
204 2841
2066 7851
3705 6183
2792 12
6173 73...

output:

1 3 7 15 7919 

result:

ok single line: '1 3 7 15 7919 '

Test #12:

score: 0
Accepted
time: 5641ms
memory: 69616kb

input:

997920
985469 20233
20233 817283
817283 511253
511253 120982
120982 270305
270305 724857
724857 386470
386470 379247
379247 451196
451196 906852
906852 512894
512894 197457
197457 988790
988790 240537
240537 627546
627546 609424
609424 716730
716730 163589
163589 460527
460527 171296
171296 570257
5...

output:

1 2 3 4 5 6 7 8 9 10 11 13 14 15 17 19 20 21 23 26 27 29 31 32 34 35 39 41 43 44 47 53 54 55 59 62 65 69 71 76 79 80 83 87 89 95 98 104 107 109 111 119 125 131 134 139 143 153 159 161 164 167 175 179 188 197 209 215 219 223 230 239 251 263 269 279 287 296 307 314 323 329 335 351 359 377 384 395 404 ...

result:

ok single line: '1 2 3 4 5 6 7 8 9 10 11 13 14 ...83 249479 332639 498959 997919 '

Test #13:

score: 0
Accepted
time: 5505ms
memory: 68452kb

input:

982800
755337 20233
20233 817283
817283 511253
511253 120982
120982 270305
270305 724857
724857 386470
386470 379247
379247 451196
451196 906852
906852 512894
512894 197457
197457 650344
650344 240537
240537 627546
627546 609424
609424 716730
716730 163589
163589 460527
460527 171296
171296 570257
5...

output:

1 2 3 4 5 6 7 8 9 11 12 13 14 15 17 19 20 23 24 25 26 27 29 34 35 38 39 41 44 47 49 51 53 55 59 62 64 69 71 74 77 79 83 89 90 99 103 104 107 111 116 119 125 129 134 139 143 149 155 167 174 179 181 188 194 199 207 209 215 224 233 239 251 259 269 272 279 299 311 314 324 335 349 350 359 363 377 389 399...

result:

ok single line: '1 2 3 4 5 6 7 8 9 11 12 13 14 ...59 245699 327599 491399 982799 '

Test #14:

score: 0
Accepted
time: 5521ms
memory: 65880kb

input:

942480
755337 20233
20233 817283
817283 511253
511253 120982
120982 270305
270305 724857
724857 386470
386470 379247
379247 451196
451196 906852
906852 512894
512894 197457
197457 650344
650344 240537
240537 627546
627546 609424
609424 716730
716730 163589
163589 460527
460527 171296
171296 570257
5...

output:

1 2 3 4 5 6 7 8 9 10 11 13 14 15 16 17 19 20 21 23 27 29 32 33 34 35 39 41 43 44 47 50 54 55 59 62 65 67 69 71 76 79 83 84 87 89 98 101 104 109 111 118 119 125 131 135 139 143 152 153 164 167 169 175 179 186 197 203 209 219 230 237 239 251 254 263 271 279 305 307 314 329 335 339 356 359 373 384 395 ...

result:

ok single line: '1 2 3 4 5 6 7 8 9 10 11 13 14 ...95 235619 314159 471239 942479 '

Test #15:

score: 0
Accepted
time: 4761ms
memory: 58404kb

input:

831600
755337 20233
20233 817283
817283 511253
511253 120982
120982 270305
270305 724857
724857 386470
386470 379247
379247 451196
451196 503174
503174 512894
512894 197457
197457 650344
650344 240537
240537 627546
627546 609424
609424 716730
716730 163589
163589 460527
460527 171296
171296 570257
5...

output:

1 2 3 4 5 6 7 8 9 10 11 13 14 15 17 19 20 21 23 24 26 27 29 32 34 35 39 41 43 44 47 49 53 54 55 59 62 65 69 71 74 76 79 83 87 89 98 99 104 107 109 111 119 125 131 134 139 143 149 153 164 167 174 175 179 188 197 199 209 215 219 224 230 239 251 263 269 274 279 296 299 307 314 329 335 349 359 377 384 3...

result:

ok single line: '1 2 3 4 5 6 7 8 9 10 11 13 14 ...19 207899 277199 415799 831599 '

Test #16:

score: 0
Accepted
time: 3987ms
memory: 52028kb

input:

720720
552329 20233
20233 665193
665193 511253
511253 120982
120982 270305
270305 300356
300356 386470
386470 379247
379247 451196
451196 503174
503174 512894
512894 197457
197457 650344
650344 240537
240537 627546
627546 609424
609424 716730
716730 163589
163589 460527
460527 171296
171296 570257
5...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 19 20 21 23 25 27 29 32 34 35 38 39 41 43 44 47 51 54 55 59 62 64 65 69 71 76 77 79 83 87 89 90 98 103 104 109 111 116 119 125 129 131 139 142 143 153 155 164 167 175 179 181 194 197 207 209 219 230 233 239 251 259 263 272 279 285 307 311 314 329 335 359 363 38...

result:

ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ...43 180179 240239 360359 720719 '

Test #17:

score: 0
Accepted
time: 4293ms
memory: 70992kb

input:

997920
985469 20233
20233 817283
985469 511253
817283 120982
20233 270305
511253 724857
817283 386470
511253 379247
985469 451196
20233 906852
817283 512894
512894 197457
270305 988790
451196 240537
20233 627546
988790 609424
120982 716730
988790 163589
240537 460527
817283 171296
511253 570257
9068...

output:

997919 

result:

ok single line: '997919 '

Test #18:

score: 0
Accepted
time: 2876ms
memory: 70092kb

input:

982800
755337 20233
755337 817283
20233 511253
755337 120982
120982 270305
20233 724857
817283 386470
724857 379247
270305 451196
451196 906852
755337 512894
386470 197457
906852 650344
512894 240537
197457 627546
20233 609424
120982 716730
120982 163589
451196 460527
270305 171296
379247 570257
650...

output:

982799 

result:

ok single line: '982799 '

Test #19:

score: 0
Accepted
time: 3625ms
memory: 67364kb

input:

942480
755337 20233
755337 817283
755337 511253
755337 120982
20233 270305
270305 724857
120982 386470
817283 379247
270305 451196
511253 906852
120982 512894
755337 197457
755337 650344
197457 240537
379247 627546
240537 609424
512894 716730
755337 163589
906852 460527
627546 171296
197457 570257
1...

output:

942479 

result:

ok single line: '942479 '

Test #20:

score: 0
Accepted
time: 3234ms
memory: 59772kb

input:

831600
755337 20233
755337 817283
755337 511253
511253 120982
817283 270305
817283 724857
817283 386470
817283 379247
386470 451196
451196 503174
755337 512894
512894 197457
270305 650344
817283 240537
817283 627546
451196 609424
627546 716730
512894 163589
512894 460527
817283 171296
609424 570257
...

output:

831599 

result:

ok single line: '831599 '

Test #21:

score: 0
Accepted
time: 2167ms
memory: 52080kb

input:

720720
552329 20233
552329 665193
20233 511253
665193 120982
120982 270305
120982 300356
511253 386470
270305 379247
120982 451196
120982 503174
270305 512894
20233 197457
503174 650344
197457 240537
240537 627546
512894 609424
511253 716730
627546 163589
270305 460527
240537 171296
379247 570257
19...

output:

720719 

result:

ok single line: '720719 '

Test #22:

score: 0
Accepted
time: 1410ms
memory: 69728kb

input:

997920
985469 20233
20233 817283
985469 511253
120982 270305
120982 724857
724857 386470
379247 451196
379247 906852
906852 512894
197457 988790
988790 240537
197457 627546
609424 716730
609424 163589
163589 460527
171296 570257
570257 859856
171296 495822
375763 608102
375763 228896
608102 885431
7...

output:

1 2 3 5 6 8 11 13 17 20 26 27 35 41 53 62 80 83 107 125 161 188 251 323 377 566 755 1133 2267 997919 

result:

ok single line: '1 2 3 5 6 8 11 13 17 20 26 27 ...3 377 566 755 1133 2267 997919 '

Test #23:

score: 0
Accepted
time: 1592ms
memory: 68960kb

input:

982800
755337 20233
20233 817283
511253 120982
511253 270305
817283 511253
724857 386470
386470 379247
451196 906852
906852 512894
724857 451196
197457 650344
197457 240537
627546 609424
627546 716730
240537 716730
163589 460527
163589 171296
570257 859856
859856 495822
163589 495822
375763 608102
3...

output:

1 2 3 4 5 9 11 12 14 19 24 25 29 38 49 51 59 64 74 77 99 129 149 155 194 259 299 324 389 649 779 974 1299 1949 3899 982799 

result:

ok single line: '1 2 3 4 5 9 11 12 14 19 24 25 ... 779 974 1299 1949 3899 982799 '

Test #24:

score: 0
Accepted
time: 756ms
memory: 66036kb

input:

942480
755337 20233
755337 817283
817283 511253
20233 120982
270305 724857
270305 386470
724857 379247
379247 451196
906852 512894
906852 197457
906852 650344
650344 240537
20233 386470
386470 240537
627546 609424
627546 716730
609424 163589
163589 460527
171296 570257
171296 859856
171296 495822
85...

output:

1 2 3 5 10 11 21 32 43 65 131 942479 

result:

ok single line: '1 2 3 5 10 11 21 32 43 65 131 942479 '

Test #25:

score: 0
Accepted
time: 753ms
memory: 59084kb

input:

831600
755337 20233
20233 817283
511253 120982
120982 270305
724857 386470
386470 379247
451196 503174
451196 512894
197457 650344
197457 240537
627546 609424
609424 716730
163589 460527
163589 171296
570257 587248
570257 495822
375763 608102
608102 228896
718816 716466
716466 661127
423372 401545
4...

output:

1 3 4 7 9 10 19 21 39 43 54 87 109 219 439 831599 

result:

ok single line: '1 3 4 7 9 10 19 21 39 43 54 87 109 219 439 831599 '

Test #26:

score: 0
Accepted
time: 2028ms
memory: 51264kb

input:

720720
552329 20233
20233 665193
665193 511253
120982 270305
120982 300356
300356 386470
379247 451196
379247 503174
503174 512894
197457 650344
197457 240537
240537 627546
609424 716730
716730 163589
716730 460527
665193 120982
270305 503174
503174 627546
627546 716730
171296 570257
587248 495822
3...

output:

1 2 3 5 6 8 10 11 12 13 17 20 21 25 27 32 35 38 41 43 51 62 65 76 77 83 90 98 116 125 131 142 153 155 181 197 230 233 251 272 285 307 363 395 428 461 467 545 571 692 818 857 923 1000 1091 1286 1385 1637 1715 2001 2573 2771 3002 3275 4003 5147 6005 9008 12011 18017 36035 720719 

result:

ok single line: '1 2 3 5 6 8 10 11 12 13 17 20 ... 9008 12011 18017 36035 720719 '

Test #27:

score: 0
Accepted
time: 4975ms
memory: 67276kb

input:

960960
755337 20233
817283 511253
120982 270305
724857 386470
379247 451196
906852 512894
197457 650344
240537 627546
609424 716730
163589 460527
171296 570257
859856 495822
375763 608102
228896 885431
716466 661127
423372 401545
76521 746296
491942 275245
876030 939228
78472 434568
327241 890219
27...

output:

1 2 3 4 5 6 7 9 10 11 12 13 14 15 19 20 21 23 25 27 29 31 32 34 38 39 41 43 47 51 54 55 59 64 65 69 76 77 79 83 87 90 95 103 104 109 111 119 129 131 139 142 153 155 159 164 167 175 181 194 207 209 219 223 230 239 259 263 272 279 285 307 311 329 335 351 363 384 389 415 419 428 439 454 461 479 519 527...

result:

ok single line: '1 2 3 4 5 6 7 9 10 11 12 13 14...19 160159 240239 480479 960959 '

Test #28:

score: 0
Accepted
time: 530ms
memory: 55896kb

input:

786240
755337 20233
20233 665193
20233 511253
120982 270305
120982 724857
120982 386470
20233 724857
379247 451196
379247 503174
503174 512894
197457 650344
197457 240537
650344 627546
451196 197457
609424 716730
163589 460527
171296 570257
587248 495822
609424 163589
460527 171296
570257 495822
120...

output:

1 2 5 6 13 20 41 786239 

result:

ok single line: '1 2 5 6 13 20 41 786239 '

Test #29:

score: 0
Accepted
time: 684ms
memory: 48700kb

input:

665280
552329 20233
665193 511253
120982 270305
300356 386470
379247 451196
503174 512894
197457 650344
240537 627546
609424 223160
163589 460527
171296 570257
587248 495822
375763 608102
228896 344015
559016 661127
423372 401545
76521 214457
491942 275245
172075 377905
78472 434568
327241 473777
27...

output:

1 3 4 6 7 9 13 15 19 27 34 39 55 69 79 111 139 279 559 665279 

result:

ok single line: '1 3 4 6 7 9 13 15 19 27 34 39 55 69 79 111 139 279 559 665279 '

Test #30:

score: 0
Accepted
time: 2839ms
memory: 67968kb

input:

970200
755337 20233
20233 817283
755337 511253
120982 270305
120982 724857
724857 386470
379247 451196
379247 906852
906852 512894
197457 650344
197457 240537
240537 627546
609424 716730
609424 163589
163589 460527
755337 120982
386470 512894
512894 650344
240537 716730
171296 570257
171296 859856
8...

output:

1 2 4 5 6 8 9 10 13 14 17 20 21 29 32 34 41 44 48 54 62 65 69 76 89 97 98 104 109 125 146 153 164 197 209 230 244 293 314 329 384 440 461 489 494 538 629 692 734 769 881 989 1077 1154 1385 1469 1616 2204 2309 2694 3233 3464 4409 4850 5389 6929 8084 9701 16169 24254 48509 970199 

result:

ok single line: '1 2 4 5 6 8 9 10 13 14 17 20 2... 9701 16169 24254 48509 970199 '

Test #31:

score: 0
Accepted
time: 564ms
memory: 67236kb

input:

957600
755337 20233
817283 511253
120982 270305
724857 386470
379247 451196
906852 512894
197457 650344
240537 627546
609424 716730
163589 460527
171296 570257
859856 495822
375763 608102
228896 885431
716466 661127
423372 401545
76521 746296
491942 275245
876030 939228
755337 817283
817283 270305
2...

output:

6 13 957599 

result:

ok single line: '6 13 957599 '

Test #32:

score: 0
Accepted
time: 471ms
memory: 69996kb

input:

1000000
985469 20233
817283 511253
120982 270305
724857 386470
379247 451196
906852 512894
197457 988790
240537 627546
609424 716730
163589 460527
20233 511253
511253 270305
120982 724857
386470 451196
379247 906852
906852 988790
197457 240537
240537 609424
716730 163589
171296 570257
570257 859856
...

output:

4 24 124 624 999999 

result:

ok single line: '4 24 124 624 999999 '