QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#381452 | #3067. Justified Jungle | I_Love_Sonechka# | TL | 4428ms | 112940kb | C++14 | 1.5kb | 2024-04-07 17:59:46 | 2024-04-07 17:59:46 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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...