QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#417455#8720. BFS 序 0grass8cow#WA 4ms27028kbC++171.7kb2024-05-22 18:59:072024-05-22 18:59:08

Judging History

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

  • [2024-05-22 18:59:08]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:27028kb
  • [2024-05-22 18:59:07]
  • 提交

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]