QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#381460 | #3067. Justified Jungle | I_Love_Sonechka# | AC ✓ | 5641ms | 70992kb | C++14 | 1.6kb | 2024-04-07 18:05:56 | 2024-04-07 18:05:56 |
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);
}
bool debug = false;
void solver() {
int n; cin >> n;
if(debug) {
n = 1e6;
}
vt<vt<int>> g(n);
for(int i = 1; i < n; ++i) {
int a, b;
if(debug) {
a = rand() % i + 1, b = i + 1;
} else {
a = read(), b = read();
}
g[--a].push_back(--b);
g[b].push_back(a);
}
vt<int> order, parent(n, -1);
queue<int> q;
q.push(0);
while(not q.empty()) {
int u = q.front(); q.pop(); order.push_back(u);
for(int to: g[u]) if(to ^ parent[u]) {
q.push(to);
parent[to] = u;
}
}
reverse(order.begin(), order.end());
vt<int> sz(n, 0);
auto check = [&](int x) -> bool {
for(int i: order) {
sz[i] = 1;
for(int from: g[i]) if(from ^ parent[i]) {
sz[i] += sz[from];
}
if(sz[i] >= x) {
if(sz[i] != x) {
return 0;
}
sz[i] = 0;
}
}
return 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: 3608kb
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: 3560kb
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: 3612kb
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: 3648kb
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: 3620kb
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: 6ms
memory: 4044kb
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: 2ms
memory: 3880kb
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: 4ms
memory: 4072kb
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: 3ms
memory: 4196kb
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: 2ms
memory: 3920kb
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: 5641ms
memory: 69616kb
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: 5505ms
memory: 68452kb
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: 5521ms
memory: 65880kb
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: 4761ms
memory: 58404kb
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: 3987ms
memory: 52028kb
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: 0
Accepted
time: 4293ms
memory: 70992kb
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:
997919
result:
ok single line: '997919 '
Test #18:
score: 0
Accepted
time: 2876ms
memory: 70092kb
input:
982800 755337 20233 755337 817283 20233 511253 755337 120982 120982 270305 20233 724857 817283 386470 724857 379247 270305 451196 451196 906852 755337 512894 386470 197457 906852 650344 512894 240537 197457 627546 20233 609424 120982 716730 120982 163589 451196 460527 270305 171296 379247 570257 650...
output:
982799
result:
ok single line: '982799 '
Test #19:
score: 0
Accepted
time: 3625ms
memory: 67364kb
input:
942480 755337 20233 755337 817283 755337 511253 755337 120982 20233 270305 270305 724857 120982 386470 817283 379247 270305 451196 511253 906852 120982 512894 755337 197457 755337 650344 197457 240537 379247 627546 240537 609424 512894 716730 755337 163589 906852 460527 627546 171296 197457 570257 1...
output:
942479
result:
ok single line: '942479 '
Test #20:
score: 0
Accepted
time: 3234ms
memory: 59772kb
input:
831600 755337 20233 755337 817283 755337 511253 511253 120982 817283 270305 817283 724857 817283 386470 817283 379247 386470 451196 451196 503174 755337 512894 512894 197457 270305 650344 817283 240537 817283 627546 451196 609424 627546 716730 512894 163589 512894 460527 817283 171296 609424 570257 ...
output:
831599
result:
ok single line: '831599 '
Test #21:
score: 0
Accepted
time: 2167ms
memory: 52080kb
input:
720720 552329 20233 552329 665193 20233 511253 665193 120982 120982 270305 120982 300356 511253 386470 270305 379247 120982 451196 120982 503174 270305 512894 20233 197457 503174 650344 197457 240537 240537 627546 512894 609424 511253 716730 627546 163589 270305 460527 240537 171296 379247 570257 19...
output:
720719
result:
ok single line: '720719 '
Test #22:
score: 0
Accepted
time: 1410ms
memory: 69728kb
input:
997920 985469 20233 20233 817283 985469 511253 120982 270305 120982 724857 724857 386470 379247 451196 379247 906852 906852 512894 197457 988790 988790 240537 197457 627546 609424 716730 609424 163589 163589 460527 171296 570257 570257 859856 171296 495822 375763 608102 375763 228896 608102 885431 7...
output:
1 2 3 5 6 8 11 13 17 20 26 27 35 41 53 62 80 83 107 125 161 188 251 323 377 566 755 1133 2267 997919
result:
ok single line: '1 2 3 5 6 8 11 13 17 20 26 27 ...3 377 566 755 1133 2267 997919 '
Test #23:
score: 0
Accepted
time: 1592ms
memory: 68960kb
input:
982800 755337 20233 20233 817283 511253 120982 511253 270305 817283 511253 724857 386470 386470 379247 451196 906852 906852 512894 724857 451196 197457 650344 197457 240537 627546 609424 627546 716730 240537 716730 163589 460527 163589 171296 570257 859856 859856 495822 163589 495822 375763 608102 3...
output:
1 2 3 4 5 9 11 12 14 19 24 25 29 38 49 51 59 64 74 77 99 129 149 155 194 259 299 324 389 649 779 974 1299 1949 3899 982799
result:
ok single line: '1 2 3 4 5 9 11 12 14 19 24 25 ... 779 974 1299 1949 3899 982799 '
Test #24:
score: 0
Accepted
time: 756ms
memory: 66036kb
input:
942480 755337 20233 755337 817283 817283 511253 20233 120982 270305 724857 270305 386470 724857 379247 379247 451196 906852 512894 906852 197457 906852 650344 650344 240537 20233 386470 386470 240537 627546 609424 627546 716730 609424 163589 163589 460527 171296 570257 171296 859856 171296 495822 85...
output:
1 2 3 5 10 11 21 32 43 65 131 942479
result:
ok single line: '1 2 3 5 10 11 21 32 43 65 131 942479 '
Test #25:
score: 0
Accepted
time: 753ms
memory: 59084kb
input:
831600 755337 20233 20233 817283 511253 120982 120982 270305 724857 386470 386470 379247 451196 503174 451196 512894 197457 650344 197457 240537 627546 609424 609424 716730 163589 460527 163589 171296 570257 587248 570257 495822 375763 608102 608102 228896 718816 716466 716466 661127 423372 401545 4...
output:
1 3 4 7 9 10 19 21 39 43 54 87 109 219 439 831599
result:
ok single line: '1 3 4 7 9 10 19 21 39 43 54 87 109 219 439 831599 '
Test #26:
score: 0
Accepted
time: 2028ms
memory: 51264kb
input:
720720 552329 20233 20233 665193 665193 511253 120982 270305 120982 300356 300356 386470 379247 451196 379247 503174 503174 512894 197457 650344 197457 240537 240537 627546 609424 716730 716730 163589 716730 460527 665193 120982 270305 503174 503174 627546 627546 716730 171296 570257 587248 495822 3...
output:
1 2 3 5 6 8 10 11 12 13 17 20 21 25 27 32 35 38 41 43 51 62 65 76 77 83 90 98 116 125 131 142 153 155 181 197 230 233 251 272 285 307 363 395 428 461 467 545 571 692 818 857 923 1000 1091 1286 1385 1637 1715 2001 2573 2771 3002 3275 4003 5147 6005 9008 12011 18017 36035 720719
result:
ok single line: '1 2 3 5 6 8 10 11 12 13 17 20 ... 9008 12011 18017 36035 720719 '
Test #27:
score: 0
Accepted
time: 4975ms
memory: 67276kb
input:
960960 755337 20233 817283 511253 120982 270305 724857 386470 379247 451196 906852 512894 197457 650344 240537 627546 609424 716730 163589 460527 171296 570257 859856 495822 375763 608102 228896 885431 716466 661127 423372 401545 76521 746296 491942 275245 876030 939228 78472 434568 327241 890219 27...
output:
1 2 3 4 5 6 7 9 10 11 12 13 14 15 19 20 21 23 25 27 29 31 32 34 38 39 41 43 47 51 54 55 59 64 65 69 76 77 79 83 87 90 95 103 104 109 111 119 129 131 139 142 153 155 159 164 167 175 181 194 207 209 219 223 230 239 259 263 272 279 285 307 311 329 335 351 363 384 389 415 419 428 439 454 461 479 519 527...
result:
ok single line: '1 2 3 4 5 6 7 9 10 11 12 13 14...19 160159 240239 480479 960959 '
Test #28:
score: 0
Accepted
time: 530ms
memory: 55896kb
input:
786240 755337 20233 20233 665193 20233 511253 120982 270305 120982 724857 120982 386470 20233 724857 379247 451196 379247 503174 503174 512894 197457 650344 197457 240537 650344 627546 451196 197457 609424 716730 163589 460527 171296 570257 587248 495822 609424 163589 460527 171296 570257 495822 120...
output:
1 2 5 6 13 20 41 786239
result:
ok single line: '1 2 5 6 13 20 41 786239 '
Test #29:
score: 0
Accepted
time: 684ms
memory: 48700kb
input:
665280 552329 20233 665193 511253 120982 270305 300356 386470 379247 451196 503174 512894 197457 650344 240537 627546 609424 223160 163589 460527 171296 570257 587248 495822 375763 608102 228896 344015 559016 661127 423372 401545 76521 214457 491942 275245 172075 377905 78472 434568 327241 473777 27...
output:
1 3 4 6 7 9 13 15 19 27 34 39 55 69 79 111 139 279 559 665279
result:
ok single line: '1 3 4 6 7 9 13 15 19 27 34 39 55 69 79 111 139 279 559 665279 '
Test #30:
score: 0
Accepted
time: 2839ms
memory: 67968kb
input:
970200 755337 20233 20233 817283 755337 511253 120982 270305 120982 724857 724857 386470 379247 451196 379247 906852 906852 512894 197457 650344 197457 240537 240537 627546 609424 716730 609424 163589 163589 460527 755337 120982 386470 512894 512894 650344 240537 716730 171296 570257 171296 859856 8...
output:
1 2 4 5 6 8 9 10 13 14 17 20 21 29 32 34 41 44 48 54 62 65 69 76 89 97 98 104 109 125 146 153 164 197 209 230 244 293 314 329 384 440 461 489 494 538 629 692 734 769 881 989 1077 1154 1385 1469 1616 2204 2309 2694 3233 3464 4409 4850 5389 6929 8084 9701 16169 24254 48509 970199
result:
ok single line: '1 2 4 5 6 8 9 10 13 14 17 20 2... 9701 16169 24254 48509 970199 '
Test #31:
score: 0
Accepted
time: 564ms
memory: 67236kb
input:
957600 755337 20233 817283 511253 120982 270305 724857 386470 379247 451196 906852 512894 197457 650344 240537 627546 609424 716730 163589 460527 171296 570257 859856 495822 375763 608102 228896 885431 716466 661127 423372 401545 76521 746296 491942 275245 876030 939228 755337 817283 817283 270305 2...
output:
6 13 957599
result:
ok single line: '6 13 957599 '
Test #32:
score: 0
Accepted
time: 471ms
memory: 69996kb
input:
1000000 985469 20233 817283 511253 120982 270305 724857 386470 379247 451196 906852 512894 197457 988790 240537 627546 609424 716730 163589 460527 20233 511253 511253 270305 120982 724857 386470 451196 379247 906852 906852 988790 197457 240537 240537 609424 716730 163589 171296 570257 570257 859856 ...
output:
4 24 124 624 999999
result:
ok single line: '4 24 124 624 999999 '