QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#639#416474#8720. BFS 序 0MaxDYFTLE_AutomatFailed.2024-05-26 20:52:182024-05-26 20:52:18

详细

Extra Test:

Accepted
time: 1ms
memory: 5612kb

input:

5
1 1 1 1
3
5 1 2 3 4 5
4 4 3 2 5
3 2 3 2

output:

Yes
Yes
No

result:

ok 3 token(s): yes count is 2, no count is 1

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#416474#8720. BFS 序 0TLE_AutomatAC ✓293ms55468kbC++203.4kb2024-05-21 21:20:322024-05-21 21:20:33

answer

#include <bits/stdc++.h>

using namespace std;

#define SZ(x) ((int)((x).size()))
#define lb(x) ((x) & (-(x)))
#define bp(x) __builtin_popcount(x)
#define bpll(x) __builtin_popcountll(x)
#define mkp make_pair
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;

const int MAXN = 3e5 + 10;

int n, q;
int fa[MAXN][21];
vector<int> G[MAXN];
int dep[MAXN];

void dfs(int u, int d) {
    dep[u] = d;
    for (auto v : G[u]) {
        dfs(v, d + 1);
    }
}

int qlca(int x, int y) {
    if (dep[x] < dep[y]) {
        swap(x, y);
    }
    int t = dep[x] - dep[y];
    for (int i = 20; i >= 0; i--) {
        if ((t >> i) & 1) {
            x = fa[x][i];
        }
    }
    if (x == y) {
        return x;
    }
    for (int i = 20; i >= 0; i--) {
        if (fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    } 
    return fa[x][0];
}

void solve() {
    cin >> n;
    for (int i = 2; i <= n; i++) {
        cin >> fa[i][0];
        G[fa[i][0]].push_back(i);
    }

    dfs(1, 0);
    for (int j = 1; j <= 20; j++) {
        for (int i = 1; i <= n; i++) {
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
        }
    }

    vector indeg(n + 1, 0);
    vector mpG(n + 1, vector<int>());
    auto sol = [&]() -> void {
        int m;
        cin >> m;
        vector p(m + 1, 0);
        for (int i = 1; i <= m; i++) {
            cin >> p[i];
        }
        
        for (int i = 1; i < m; i++) {
            if (dep[p[i]] > dep[p[i + 1]]) {
                cout << "No" << '\n';
                return ;
            }
        }

        set<int> s;
        for (int i = 1; i < m; i++) {
            int x = p[i], y = p[i + 1];
            if (dep[x] != dep[y]) {
                continue;
            }
            int lca = qlca(x, y);

            // printf("x = %d, y = %d, lca = %d\n", x, y, lca);
            for (int j = 20; j >= 0; j--) {
                if (dep[fa[x][j]] > dep[lca]) {
                    x = fa[x][j];
                }
            }
            for (int j = 20; j >= 0; j--) {
                if (dep[fa[y][j]] > dep[lca]) {
                    y = fa[y][j];
                }
            }
            // printf("u = %d, v = %d\n", x, y);

            s.insert(x);
            s.insert(y);
            indeg[y]++;
            mpG[x].push_back(y);
        }

        queue<int> q;
        for (auto x : s) {
            if (!indeg[x]) {
                q.push(x);
            }
        }
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto v : mpG[u]) {
                indeg[v]--;
                if (!indeg[v]) {
                    q.push(v);
                }
            }
        }

        bool flg = true;
        for (auto x : s) {
            if (indeg[x]) {
                flg = false;
                break;
            }
        }

        cout << (flg ? "Yes" : "No") << '\n';

        for (auto x : s) {
            mpG[x].clear();
            indeg[x] = 0;
        }
    };

    cin >> q;
    while (q--) {
        sol();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    while (T--) solve();
    return 0;
}