QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#381450#3067. Justified JungleI_Love_Sonechka#TL 4592ms113072kbC++141.1kb2024-04-07 17:56:262024-04-07 17:56:27

Judging History

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

  • [2024-04-07 17:56:27]
  • 评测
  • 测评结果:TL
  • 用时:4592ms
  • 内存:113072kb
  • [2024-04-07 17:56:26]
  • 提交

answer

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

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

void solver() {
	int n; cin >> n;
	vt<vt<int>> g(n);
	for(int i = 1; i < n; ++i) {
		int a, b; cin >> a >> b;
		g[--a].push_back(--b);
		g[b].push_back(a);
	}
	vt<int> order, parent(n, -1);
	auto dfs = [&](auto self, int e, int p) -> void {
		parent[e] = p;
		for(int to: g[e]) if(to ^ p) {
			self(self, to, e);
		}
		order.push_back(e);
	};
	dfs(dfs, 0, 0);
	auto check = [&](int x) -> bool {
		bool flag = true;
		vt<int> sz(n, 0);
		for(int i: order) {
			sz[i] = 1;
			for(int from: g[i]) if(from ^ parent[i]) {
				sz[i] += sz[from];
			}
			if(sz[i] >= x) {
				flag = flag && sz[i] == x;
				sz[i] = 0;
			}
		}
		return flag && 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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3628kb

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: 3636kb

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: 3868kb

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: 3568kb

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: 3576kb

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: 8ms
memory: 4216kb

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: 8ms
memory: 4180kb

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: 5ms
memory: 4076kb

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: 7ms
memory: 4044kb

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: 7ms
memory: 3996kb

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: 4592ms
memory: 113072kb

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: 3608ms
memory: 112016kb

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: 4580ms
memory: 93464kb

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: -100
Time Limit Exceeded

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:


result: