QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#417455 | #8720. BFS 序 0 | grass8cow# | WA | 4ms | 27028kb | C++17 | 1.7kb | 2024-05-22 18:59:07 | 2024-05-22 18:59:08 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
vector<int>g[501000];
int f[500100][20],d[500100];
#define pb push_back
void dfs(int x){
for(int v:g[x]){
f[v][0]=x,d[v]=d[x]+1;
for(int i=1;i<20;i++)f[v][i]=f[f[v][i-1]][i-1];
dfs(v);
}
}
int lca(int u,int v){
if(d[u]<d[v])swap(u,v);int a=d[u]-d[v];
for(int i=19;i>=0;i--)if((a>>i)&1)u=f[u][i];if(u==v)return u;
for(int i=19;i>=0;i--)if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
return f[u][0];
}
int zj(int x,int t){
for(int i=19;i>=0;i--)
if(f[t][i]&&d[f[t][i]]>d[x])t=f[t][i];
return t;
}
#define pb push_back
int n,tp[501000],S,a[500100],rk[501000],b[501000],ru[501000];
vector<int>cj[501000];
int main(){
scanf("%d",&n);
for(int i=2,f;i<=n;i++)scanf("%d",&f),g[f].pb(i);
dfs(1);
int q;scanf("%d",&q);
for(int i=1;i<=n;i++)tp[i]=q+555;
while(q--){
scanf("%d",&S);
for(int i=1;i<=S;i++)scanf("%d",&a[i]),b[i]=a[i];
sort(b+1,b+S+1);
bool fl=1;
for(int i=1;i<S;i++)fl&=(d[a[i]]<=d[a[i+1]]),fl&=(b[i]!=b[i+1]);
if(!fl){puts("No");continue;}
int e=0;
for(int i=1;i<S;i++)if(d[a[i]]==d[a[i+1]]){
int lc=lca(a[i],a[i+1]),u=zj(a[i],lc),v=zj(a[i+1],lc);
if(tp[u]!=q)tp[u]=q,rk[u]=++e,ru[e]=0,cj[e].clear();
if(tp[v]!=q)tp[v]=q,rk[v]=++e,ru[e]=0,cj[e].clear();
cj[rk[u]].pb(rk[v]),ru[rk[v]]++;
}
queue<int>z;
for(int i=1;i<=e;i++)if(!ru[i])z.push(i);
int vc=0;
while(!z.empty()){
int u=z.front();z.pop();vc++;
for(int v:cj[u])if(!(--ru[v]))z.push(v);
}
puts((vc==e)?"Yes":"No");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 27028kb
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:
No Yes No No No No No No No No
result:
wrong answer expected YES, found NO [3rd token]