QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#641294#8720. BFS 序 0neetmanWA 0ms11892kbC++143.0kb2024-10-14 19:42:132024-10-14 19:42:14

Judging History

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

  • [2024-10-14 19:42:14]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:11892kb
  • [2024-10-14 19:42:13]
  • 提交

answer

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 3e5 + 5;
int n, m, q, tot, top;
int fa[N][20], head[N], dep[N], idx[N];
int vis[N], sta[N*2], maxn[N]; 
struct edge{
    int u, v;
}e[N];

int cnt;
void addedge(int x, int y){
    e[++cnt].u = head[x];
    e[cnt].v = y;
    head[x] = cnt;
}

void dfs(int x){
    for(int i = 1; fa[x][i] = fa[fa[x][i-1]][i-1]; i ++);
    for(int i = head[x]; i; i = e[i].u){
        int to = e[i].v;
        dep[to] = dep[x] + 1;
        dfs(to);
    }
    idx[x] = ++tot;
}

int lca(int x, int y){
    if(dep[x] != dep[y]){
        if(dep[x] < dep[y]) swap(x, y);
        for(int i = 19; ~i; i --){
            if(dep[fa[x][i]] >= dep[y])
                x = fa[x][i];
        }
    }
    if(x == y) return x;
    for(int i = 19; ~i; i --)
        if(fa[x][i] != fa[y][i]){
            x = fa[x][i];
            y = fa[y][i];
        }
    return fa[x][0];
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> n;
    for(int i = 2; i <= n; i ++){
        cin >> fa[i][0];
        addedge(fa[i][0], i);
    }
    dep[1] = 1;
    dfs(1);
    cin >> q;
    bool jud;
    while(q --){
        cin >> m; jud = 1;
        for(int i = 1; i <= m; i ++){
            cin >> sta[i];
            maxn[sta[i]] = dep[sta[i]];
            if(vis[sta[i]])
                jud = 0;
            vis[sta[i]] = 1;
        }
        top = m;
        // cout << "q = " << q << " jud = " << jud << '\n';
        for(int i = m - 1; i; i --){
            int LCA = lca(sta[i], sta[top]);
            // cout << "TEST!! " << sta[i] << " " << sta[top] << " " << maxn[sta[i]] << " " << maxn[sta[top]] << '\n';
            if(LCA == sta[i]){
                sta[top] = sta[i];
                continue;
            }
            if(LCA == sta[top]){
                if(maxn[sta[top]] < maxn[sta[i]])
                    jud = 0;
                maxn[sta[top]] = maxn[sta[i]];
            }
            else{
                if(maxn[sta[top]] < maxn[sta[i]])
                    jud = 0;
                sta[++top] = LCA;
                maxn[sta[top]] = maxn[sta[i]];
            }
        }
        if(jud) cout << "Yes\n";
        else cout << "No\n";
        for(int i = 1; i <= top; i ++)
            maxn[sta[i]] = vis[sta[i]] = 0;
        // sort(sta + 1, sta + 1 + m, [](int x, int y){
        //     return idx[x] < idx[y];
        // });
        // siz = m;
        // for(int i = 1; i < m; i ++){
        //     int LCA = lca(sta[i], sta[i + 1]);
        //     if(!is[LCA]){
        //         sta[++siz] = LCA;
        //         is[LCA] = 1;
        //     }
        //     if(!nex[sta[i]])
        // }
        // for(int i = 1; i <= siz; i ++){
        //     is[sta[i]] = nex[sta[i]] = L[sta[i]] = R[sta[i]] = in[sta[i]] = 0;
        // }
    }
    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
Wrong Answer
time: 0ms
memory: 11892kb

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
Yes

result:

wrong answer expected YES, found NO [3rd token]