QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#479067#8716. 树Nienie0730RE 0ms0kbC++173.7kb2024-07-15 14:37:052024-07-15 14:37:06

Judging History

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

  • [2024-07-15 14:37:06]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-07-15 14:37:05]
  • 提交

answer

    #include <bits/stdc++.h>
    using namespace std;

    #define x first
    #define y second

    typedef long long LL;
    typedef pair<int, int> PII;
    typedef pair<double, double> PDD;

    const int N = 2e5 + 10, M = 2e5 + 10, INF = 0x3f3f3f3f;
    const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
    const double eps = 1e-8;

    int n, m, q;
    int h[N], e[N << 1], ne[N << 1], idx;
    int A[N], B[N];
    int depth[N], fa[N][21];

    void add(int a, int b) {
        e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    }

    void bfs(int u) {
        memset(depth, 0x3f, sizeof depth);
        queue<int> q;
        q.push(u);
        depth[0] = 0;
        depth[u] = 1;
        while (q.size()) {
            int t = q.front();
            q.pop();
            for (int i = h[t];i != -1;i = ne[i]) {
                int j = e[i];
                if (depth[j] > depth[t] + 1) {
                    depth[j] = depth[t] + 1;
                    q.push(j);
                    fa[j][0] = t;
                    for (int k = 1;k < 20;k++) {
                        fa[j][k] = fa[fa[j][k - 1]][k - 1];
                    }
                }
            }
        }
    }

    int lca(int a, int b) {
        if (depth[a] < depth[b]) swap(a, b);
        for (int k = 19;k >= 0;k--) {
            if (depth[fa[a][k]] >= depth[b])
                a = fa[a][k];
        }
        if (a == b) return a;
        for (int k = 19;k >= 0;k--) {
            if (fa[a][k] != fa[b][k]) {
                a = fa[a][k];
                b = fa[b][k];
            }
        }
        return fa[a][0];
    }

    int check(int a, int b) {
        int p = lca(a, b);
        if (p == b) return 0;
        return 1;
    }

    int change(int i, bool ok) {
        int t = check(B[i - 2], B[i - 1]);

        if (t == 1) {
            if (lca(B[i - 1], B[i]) == B[i - 1]) A[i - 1] = 0;
        }
        else {
            int tt = lca(B[i - 2], B[i]);
            if (tt == B[i - 1]) {
                A[i - 1] = 0;
            }
            else {
                tt = lca(B[i - 1], tt);
                if (tt != B[i - 1]) A[i - 1] = 0;
            }
        }

        if (ok) A[i] = 1;
    }

    void solve() {
        cin >> n >> m >> q;
        memset(h, -1, sizeof h);

        for (int i = 1;i < n;i++) {
            int a, b;
            cin >> a >> b;
            add(a, b);
            add(b, a);
        }

        for (int i = 1;i <= m;i++) cin >> B[i];

        bfs(1);
        
        A[1] = A[2] = 1;
        for (int i = 3;i <= m;i++)
            change(i, false);

        int sum = 0;
        for (int i = 1;i <= m;i++) sum += A[i];

        // for (int j = 1;j <= q;j++) {
        //     int a, b;
        //     cin >> a >> b;
        //     B[a] = b;

        //     int temp = 0;
        //     temp += A[a], A[a] = 1;
        //     if (a > 1) temp += A[a - 1], A[a - 1] = 1;
        //     if (a < m) temp += A[a + 1], A[a + 1] = 1;

        //     if (a > 2) {
        //         change(a, false);
        //     }

        //     if (a + 1 > 2 && a + 1 <= m) {
        //         change(a + 1, false);
        //     }

        //     if (a + 2 <= m) {
        //         change(a + 2, false);
        //     }

        //     int now = 0;
        //     now += A[a];
        //     if (a > 1) now += A[a - 1];
        //     if (a < m) now += A[a + 1];

        //     sum += now - temp;

        //     cout << sum << "\n";
        // }

    }

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

詳細信息

Test #1:

score: 0
Runtime Error

input:

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

output:


result: