QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#61201 | #3067. Justified Jungle | chiranko# | TL | 16ms | 27500kb | C++ | 1.1kb | 2022-11-11 14:43:40 | 2022-11-11 14:43:42 |
Judging History
answer
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long LL;
const int maxn = 1e6 + 5;
vector<int> E[maxn];
int fl, n;
int dfs(int x, int fr, int y)
{
if(!fl)
return 0;
int res = 1;
for(auto &v : E[x]){
if(v == fr)
continue;
res += dfs(v, x, y);
}
// cout << x << " " << fr << " " << y << " " << res << endl;
if(res <= y)
return (res == y ? 0 : res);
else{
fl = 0;
return res;
}
}
inline int read(){
int x=0,f=1;char ch=' ';
while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return f==1?x:-x;
}
int main()
{
n = read();
for(int i = 1; i < n; ++i){
int a, b;
a = read(), b = read();
E[a].pb(b), E[b].pb(a);
}
vector<int> ans;
for(int i = 1; i <= n; ++i){
if(!(n % (i + 1))){
fl = 1;
dfs(1, 0, n / (i + 1));
if(fl)
ans.pb(i);
}
}
for(int i = 0; i < ans.size(); ++i){
printf("%d", ans[i]);
if(i != ans.size() - 1)
printf(" ");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 6ms
memory: 26972kb
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: 5ms
memory: 27096kb
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: 4ms
memory: 27092kb
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: 4ms
memory: 26880kb
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: 5ms
memory: 26896kb
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: 4ms
memory: 26896kb
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: 13ms
memory: 27284kb
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: 5ms
memory: 27372kb
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: 11ms
memory: 27500kb
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: 13ms
memory: 27288kb
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: 16ms
memory: 27232kb
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...