QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#416300 | #8720. BFS 序 0 | zjx666 | RE | 0ms | 0kb | C++11 | 1.7kb | 2024-05-21 19:01:56 | 2024-05-21 19:01:57 |
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
*/
详细
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