QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#343507#3067. Justified JunglePetroTarnavskyi#TL 10ms4216kbC++201.1kb2024-03-02 17:51:052024-03-02 17:51:05

Judging History

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

  • [2024-03-02 17:51:05]
  • 评测
  • 测评结果:TL
  • 用时:10ms
  • 内存:4216kb
  • [2024-03-02 17:51:05]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int N = 1 << 20;
VI g[N];

int dfs(int v, int p, int s)
{
	int sz = 1;
	for (auto to : g[v])
		if (to != p)
			sz += dfs(to, v, s);
	if (sz == s)
		return 0;
	return sz;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;
	FOR (i, 0, n - 1)
	{
		int u, v;
		cin >> u >> v;
		u--, v--;
		g[u].PB(v);
		g[v].PB(u);
	}
	VI d;
	FOR (i, 1, n)
	{
		if (n % i == 0)
			d.PB(i);
	}
	VI ans;
	for (auto div : d)
	{
		if (dfs(0, -1, div) == 0)
			ans.PB(div);
	}
	reverse(ALL(ans));
	FOR (i, 0, SZ(ans))
	{
		if (i)
			cout << ' ';
		cout << (n / ans[i]) - 1;
	}
	cout << '\n';
	
	return 0;
}




詳細信息

Test #1:

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

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

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

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

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

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

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

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

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

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

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

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

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:


result: