UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#212810#3829. Cchentairansz00ms0kbC++1.1kb2024-10-20 11:41:592024-10-20 12:45:24

answer

#include<bits/stdc++.h>
using namespace std;
int n,zx;
struct tree
{
	int p,fas;
	vector<int>ch;
	vector<int>chs;
	tree(){ ch.clear(); }
}t[100050];
int v[100050];
int cchs(int x)
{
	if(v[x]!=-1)return v[x];
	int cnt=0;
	for(int i=0;i<t[x].ch.size();i++)
	{
		cnt+=cchs(t[x].ch[i])+1;
	}
	v[x]=cnt;
	return cnt;
}
int cfas(int x)
{
	int cnt=0;
	for(int i=0;i<t[x].chs.size();i++)
	{
		cnt+=t[x].chs[i];
	}
	return n-cnt-1;
}
int main()
{
	memset(v,-1,sizeof(v));
	cin>>n;
	for(int i=2;i<=n;i++)
	{
		cin>>t[i].p;
		t[t[i].p].ch.push_back(i);
	}
	int z=0;
	for(int i=1;i<=n;i++)
	{
		int f=0;
		for(int j=0;j<t[i].ch.size();j++)
		{
			int l=cchs(t[i].ch[j])+1;
			t[i].chs.push_back(l);//cout<<l<<' ';
			if(l>n/2)f=1;
		}//puts("");
		t[i].fas=cfas(i);//cout<<"fas:"<<t[i].fas<<'\n';
		if(f==0&&z==0&&t[i].fas<=n/2)
		{
			zx=i;
			cout<<i<<' ';
			z=1;
		}
	}
	if(n%2==0)
	{
		cout<<0;
		return 0;
	}
	int mn=2138193810;
	for(int i=0;i<t[zx].ch.size();i++)
	{
		mn= min(mn,t[zx].ch[i]);
	}
	if(mn!=zx)
	{
		cout<<1;
	}
	else
	{
		cout<<0;
	}
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 0
Memory Limit Exceeded

Test #1:

score: 0
Memory Limit Exceeded

input:

5
3 1
1 5
2 4
5 4

output:


result:


Subtask #2:

score: 0
Memory Limit Exceeded

Test #4:

score: 0
Memory Limit Exceeded

input:

100
63 38
17 33
44 12
9 66
21 98
2 49
68 67
75 42
78 25
92 6
67 17
90 19
48 51
83 9
20 94
68 4
64 58...

output:


result:


Subtask #3:

score: 0
Memory Limit Exceeded

Test #10:

score: 0
Memory Limit Exceeded

input:

1000
228 978
939 994
911 13
8 806
680 958
779 832
673 924
627 806
354 476
320 218
766 848
171 944
90...

output:


result:


Subtask #4:

score: 0
Memory Limit Exceeded

Test #16:

score: 0
Memory Limit Exceeded

input:

100000
44881 88880
79640 18741
56510 31493
27649 50461
7015 98523
26337 91384
17594 52397
37312 3409...

output:


result:


Subtask #5:

score: 0
Runtime Error

Test #22:

score: 0
Runtime Error

input:

1000000
198444 939986
569807 470692
847908 557044
739959 80274
772656 222835
832266 382872
267873 10...

output:


result: