QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#864541 | #7320. Prime Tree | C1942huangjiaxu | WA | 75ms | 35356kb | C++14 | 1.1kb | 2025-01-20 18:35:59 | 2025-01-20 18:35:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
typedef unsigned long long ull;
mt19937_64 rnd(0x66ccff);
inline ull Rnd(ull x){
x^=x<<13;
x^=x>>7;
x^=x<<17;
return x;
}
int gcd(int x,int y){
return y?gcd(y,x%y):x;
}
int n,m,a[N],sz[N],b[N],ans;
ull f[N],V,va[N];
vector<int>e[N];
void dfs(int x){
}
bool check(int y){
for(int x=n;x;--x)if(sz[x]>=y){
if(sz[x]==y){
if(f[x]!=va[y])return false;
}
ull o=V;
for(auto v:e[x])if(sz[v]<y)o+=Rnd(f[v]);
if(o!=va[y])return false;
}
return true;
}
void solve(){
V=rnd(),ans=1;
for(int i=1;i<=n;++i)e[i].clear();
for(int i=2,x;i<=n;++i){
scanf("%d",&x);
e[x].push_back(i);
}
for(int x=n;x;--x){
sz[x]=1,f[x]=V;
for(auto v:e[x]){
sz[x]+=sz[v];
f[x]+=Rnd(f[v]);
}
va[sz[x]]=f[x];
}
for(int i=1;i<=n;++i)b[i]=sz[i];
sort(b+1,b+n+1);
for(int i=n-1;i;--i)b[i]=gcd(b[i],b[i+1]);
m=unique(b+1,b+n+1)-b-1;
for(int i=2;i<m;++i)if(b[i])++ans;
printf("%d\n",ans);
}
int main(){
while(scanf("%d",&n)!=EOF)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 35320kb
input:
12 1 1 1 1 2 2 4 5 5 6 10 3 1 1 6 1 1 1 2 3 13 1 1 1 2 2 3 3 4 5 6 7 8
output:
3 1 2 1
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 68ms
memory: 35272kb
input:
168 1 2 3 3 2 1 1 8 9 10 10 9 8 1 15 16 17 17 16 15 15 22 23 24 24 23 22 1 29 30 31 31 30 29 29 36 37 38 38 37 36 29 43 44 45 45 44 43 43 50 51 52 52 51 50 29 57 58 59 59 58 57 57 64 65 66 66 65 64 57 71 72 73 73 72 71 71 78 79 80 80 79 78 1 85 86 87 87 86 85 85 92 93 94 94 93 92 85 99 100 101 101 1...
output:
5 1 4 1 3 3 1 7 2 2 5 2 3 1 3 2 2 4 3 1 5 3 2 5 4 2 4 2 3 2 6 8 3 7 2 1 3 2 6 6 9 4 5 3 4 1 2 1 1 2 1 4 3 1 1 2 7 3 2 2 1 3 3 4 5 2 4 2 3 2 4 2 2 1 5 5 3 3 2 3 1 4 8 6 2 2 2 1 3 4 2 2 5 1 2 4 2 2 8 5 2 1 1 4 2 3 3 2 4 1 2 3 4 3 2 2 2 3 3 3 3 3 1 2 2 6 2 5 2 2 3 4 3 2 2 1 2 3 4 6 4 3 1 4 3 2 3 1 1 2 ...
result:
ok 1960 lines
Test #3:
score: 0
Accepted
time: 54ms
memory: 33648kb
input:
100 1 1 1 1 1 6 6 6 6 1 11 11 11 11 11 16 16 16 16 11 21 21 21 21 21 26 26 26 26 21 31 31 31 31 31 36 36 36 36 21 41 41 41 41 41 46 46 46 46 1 51 51 51 51 51 56 56 56 56 51 61 61 61 61 61 66 66 66 66 61 71 71 71 71 71 76 76 76 76 71 81 81 81 81 81 86 86 86 86 71 91 91 91 91 91 96 96 96 96 100 1 1 3 ...
output:
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 ...
result:
ok 10000 lines
Test #4:
score: 0
Accepted
time: 55ms
memory: 35044kb
input:
36 1 1 3 1 5 5 7 1 9 9 11 1 13 13 15 13 17 17 19 13 21 21 23 1 25 25 27 25 29 29 31 25 33 33 35 36 1 2 1 4 5 1 7 8 7 10 11 1 13 14 13 16 17 1 19 20 19 22 23 19 25 26 25 28 29 19 31 32 31 34 35 36 1 1 3 1 5 5 7 1 9 9 11 1 13 13 15 13 17 17 19 13 21 21 23 1 25 25 27 25 29 29 31 25 33 33 35 36 1 1 3 3 ...
output:
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 ...
result:
ok 27777 lines
Test #5:
score: 0
Accepted
time: 66ms
memory: 34632kb
input:
23 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 90 1 2 1 4 5 1 7 8 1 10 11 10 13 14 10 16 17 1 19 20 19 22 23 19 25 26 1 28 29 28 31 32 28 34 35 1 37 38 37 40 41 37 43 44 1 46 47 46 49 50 46 52 53 46 55 56 55 58 59 55 61 62 46 64 65 64 67 68 64 70 71 46 73 74 73 76 77 73 79 80 46 82 83 82 85 86 82 88...
output:
1 4 1 4 1 3 3 1 2 2 2 1 4 2 3 4 4 6 3 1 3 2 4 3 5 1 1 1 3 1 1 2 2 4 3 3 1 4 2 3 1 5 1 1 3 2 2 1 1 2 1 3 3 3 4 1 2 3 2 3 2 1 2 2 1 5 1 2 2 1 1 2 5 2 4 2 2 2 1 2 1 3 2 1 4 1 4 2 2 2 1 3 2 3 3 3 2 3 3 3 2 2 1 1 4 2 2 2 2 2 1 3 2 4 1 1 2 3 1 2 1 3 3 4 3 1 3 2 4 6 2 2 2 2 3 4 2 3 1 5 2 5 3 4 2 2 1 1 2 1 ...
result:
ok 18231 lines
Test #6:
score: -100
Wrong Answer
time: 75ms
memory: 35356kb
input:
339 1 1 2 3 2 1 2 3 6 1 8 8 11 7 14 9 10 8 13 16 18 19 22 19 21 23 27 24 20 21 24 30 32 29 32 33 27 35 35 38 36 34 38 36 41 37 46 48 48 41 49 51 46 52 55 55 47 49 55 57 57 58 60 58 61 61 60 61 60 59 64 67 64 72 70 71 76 77 70 74 71 72 78 76 78 84 81 77 89 86 84 85 86 93 92 96 90 95 97 91 91 98 102 9...
output:
1 2 2 4 3 2 2 3 5 1 2 3 3 5 3 1 4 1 2 3 2 2 2 5 2 5 4 3 2 2 2 4 2 3 1 5 3 2 3 2 4 2 1 2 3 2 1 4 3 3 2 2 2 1 1 2 3 3 1 3 2 2 2 5 1 2 1 1 4 3 2 1 1 3 1 2 2 4 3 6 3 1 3 3 2 1 5 2 3 6 3 3 2 2 2 1 1 1 1 3 3 1 1 4 1 1 2 3 5 2 1 1 3 2 2 2 4 3 4 1 3 1 2 5 1 1 2 3 4 1 2 3 2 3 1 1 4 2 2 1 5 3 1 2 1 2 1 2 3 5 ...
result:
wrong answer 2nd lines differ - expected: '1', found: '2'