QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#381452#3067. Justified JungleI_Love_Sonechka#TL 4428ms112940kbC++141.5kb2024-04-07 17:59:462024-04-07 17:59:46

Judging History

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

  • [2024-04-07 17:59:46]
  • 评测
  • 测评结果:TL
  • 用时:4428ms
  • 内存:112940kb
  • [2024-04-07 17:59:46]
  • 提交

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);
}

void solver() {
	int n; cin >> n;
	vt<vt<int>> g(n);
	for(int i = 1; i < n; ++i) {
		int a, b; 
		a = read(), b = read();
		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;
}

详细

Test #1:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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:


result: