QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#416300#8720. BFS 序 0zjx666RE 0ms0kbC++111.7kb2024-05-21 19:01:562024-05-21 19:01:57

Judging History

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

  • [2024-05-21 19:01:57]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-05-21 19:01:56]
  • 提交

answer

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int maxn=500010;
int d[maxn];
vector<int>e[maxn];
vector<int>e2[maxn];
int a[maxn];
int f[maxn][30];
int vi[maxn];
queue<int>q;
int r[maxn];
int n;
void bfs(int x,int deep)
{
	d[x]=deep+1;
	for(int i=1;i<=25;i++)
	{
		f[x][i]=f[f[x][i-1]][i-1];
	}
	for(int i=0;i<e[x].size();i++)
	{
		f[e[x][i]][0]=x;
		bfs(e[x][i],d[x]);
	}
}
bool lca(int x,int y)
{
	for(int i=25;i>=0;i--)
	{
		if(f[x][i]!=f[y][i])
		{
			x=f[x][i];
			y=f[y][i];
		}
	}
	e2[x].push_back(y);
	r[y]++;
}
void ch2(int x)
{
	for(int i=0;i<e2[x].size();i++)
	{
		r[e2[x][i]]--;
		if(!r[e2[x][i]])q.push(e2[x][i]);
	}
}
bool ch()
{
	int ans=0;
	for(int i=1;i<=n;i++)
	  if(r[i]==0)q.push(i);
	while(q.size())
	{
		int x=q.front();
		q.pop();
		ch2(x);
		ans++;
	}
	if(ans!=n)return 0;
	else return  1;
	
}
signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=2;i<=n;i++)
	{
		int x;
		cin>>x;
	    e[x].push_back(i);
	}
	f[1][0]=1;
	bfs(1,0); 
	int q1;
    cin>>q1;
    while(q1--)
    {
    	for(int i=1;i<=n;i++)
		{
			e2[i].clear();
			r[i]=0;
			vi[i]=0;
		}
    	int m,v=1;
    	cin>>m;
    	for(int i=1;i<=m;i++)
    	{
    		cin>>a[i];
    		if(vi[a[i]]||a[i]<1||a[i]>n)v=0;
    		vi[a[i]]=1;
		}
		for(int i=2;i<=m&&v;i++)
		{
			if(d[a[i]]==d[a[i-1]])
			{
				lca(a[i-1],a[i]);
			}
			else if(d[a[i]]>d[a[i-1]])continue;
			else 
			{
				v=0;
				break;
			}
		}
		if(!v)cout<<"NO\n";
		else if(!ch())cout<<"NO\n";
		else cout<<"YES\n";
	}
	return 0;
}
/*
6
1 1 3 2 4
10
4 3 6 2 5
1 4
3 2 4 5
5 2 5 4 6 3
3 1 4 2
3 5 6 3
5 4 5 2 6 1
4 4 3 2 5
4 4 6 2 3
3 3 2 6
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

6
1 1 3 2 4
10
4 3 6 2 5
1 4
3 2 4 5
5 2 5 4 6 3
3 1 4 2
3 5 6 3
5 4 5 2 6 1
4 4 3 2 5
4 4 6 2 3
3 3 2 6

output:


result: