Submission #963613

#	Time	Username	Problem	Language	Result	Execution time	Memory
963613		MisterReaper	Synchronization (JOI13_synchronization)	C++17	100 / 100	273 ms	24024 KiB

synchronization

#include <bits/stdc++.h>
using i64 = long long;

constexpr int maxN = 1E5 + 5;
constexpr int L = 20;

std::vector<int> adj[maxN];
int par[maxN][L], tin[maxN], tout[maxN], info[maxN], lastsync[maxN];
int X[maxN], Y[maxN];
bool active[maxN];

int tree[maxN * 2];
struct fenwick {
    int n;
    fenwick(int _n) : n(_n + 1) {}
    void modify(int p, int v) {
        for(++p; p <= n; p += p & -p) {
            tree[p] += v;
        }
    }
    int query(int p) {
        int res = 0;
        for(++p; p > 0; p -= p & -p) {
            res += tree[p];
        }
        return res;
    }
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, M, Q;
    std::cin >> N >> M >> Q;

    for(int i = 0; i < N - 1; i++) {
        std::cin >> X[i] >> Y[i];
        --X[i], --Y[i];
        adj[X[i]].emplace_back(Y[i]);
        adj[Y[i]].emplace_back(X[i]);
    }

    int t = 0;
    auto dfs = [&](auto&& self, int v) -> void {
        tin[v] = t++;
        info[v] = 1;
        for(int u : adj[v]) {
            if(u == par[v][0]) {
                continue;
            }
            par[u][0] = v;
            self(self, u);
        }
        tout[v] = t++;
    };

    dfs(dfs, 0);

    for(int lg = 1; lg < L; lg++) {
        for(int v = 0; v < N; v++) {
            par[v][lg] = par[par[v][lg - 1]][lg - 1];
        }
    }

    fenwick fen(2 * N);
    for(int i = 0; i < N; i++) {
        fen.modify(tin[i], -1);
        fen.modify(tout[i], 1);
    }

    auto get = [&](int v) -> int {
        for(int lg = L - 1; lg >= 0; lg--) {
            if(fen.query(tin[par[v][lg]]) == fen.query(tin[v])) {
                v = par[v][lg];
            }
        }
        return v;
    };

    for(int i = 0; i < M; i++) {
        int D;
        std::cin >> D;
        --D;
        int u = X[D], v = Y[D];
        if(par[u][0] == v) {
            std::swap(u, v);
        }

        // std::cerr << u << ' ' << v << '\n';
        if(active[D]) {
            info[v] = lastsync[D] = info[get(u)];
            fen.modify(tin[v], -1);
            fen.modify(tout[v], 1);
        } else {
            int newval = info[get(u)] + info[v] - lastsync[D];
            info[get(u)] = newval;
            fen.modify(tin[v], 1);
            fen.modify(tout[v], -1);
        }
        active[D] = !active[D];
        // for(int w = 0; w < N; w++) {
        //     std::cerr << get(w) << " \n"[w + 1 == N];
        // }
        // for(int w = 0; w < 2 * N; w++) {
        //     std::cerr << fen.query(w) << " \n"[w + 1 == 2 * N];
        // }
        // for(int w = 0; w < N; w++) {
        //     std::cerr << info[get(w)] << " \n"[w + 1 == N];
        // }
    }

    for(int i = 0; i < Q; i++) {
        int C;
        std::cin >> C;
        --C;
        std::cout << info[get(C)] << '\n';
    }

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40