QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#864541#7320. Prime TreeC1942huangjiaxuWA 75ms35356kbC++141.1kb2025-01-20 18:35:592025-01-20 18:35:59

Judging History

你现在查看的是最新测评结果

  • [2025-01-20 18:35:59]
  • 评测
  • 测评结果:WA
  • 用时:75ms
  • 内存:35356kb
  • [2025-01-20 18:35:59]
  • 提交

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;
}

詳細信息

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'