QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#381450 | #3067. Justified Jungle | I_Love_Sonechka# | TL | 4592ms | 113072kb | C++14 | 1.1kb | 2024-04-07 17:56:26 | 2024-04-07 17:56:27 |
Judging History
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;
}
詳細信息
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...