Submission #599893

#	Time	Username	Problem	Language	Result	Execution time	Memory
599893		timmyfeng	Synchronization (JOI13_synchronization)	C++17	100 / 100	264 ms	36416 KiB

synchronization

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

const int N = 2e5;

int node[N], parent[N], sub[N], in[N];
vector<pair<int, int>> adj[N];

void dfs_sub(int u) {
    sub[u] = 1;
    for (auto &e : adj[u]) {
        auto [c, i] = e;
        parent[c] = u, node[i] = c;
        adj[c].erase(find(adj[c].begin(), adj[c].end(), pair<int, int>{u, i}));
        dfs_sub(c);
        sub[u] += sub[c];
        if (sub[c] > sub[adj[u][0].first]) {
            swap(adj[u][0], e);
        }
    }
}

int head[N], tour[N];

void dfs_hld(int u) {
    static int t = 0;
    tour[t] = u, in[u] = t++;
    for (auto [c, i] : adj[u]) {
        head[c] = (c == adj[u][0].first) ? head[u] : c;
        dfs_hld(c);
    }
}

set<int> off[N];

int get_root(int u) {
    while (off[head[u]].empty() || *off[head[u]].begin() > in[u]) {
        u = parent[head[u]];
    }
    return tour[*--off[head[u]].upper_bound(in[u])];
}

int answer[N], common[N];
bool on[N];

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

    int n, m, q; cin >> n >> m >> q;

    for (int i = 0; i < n - 1; ++i) {
        int u, v; cin >> u >> v; --u, --v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    dfs_sub(0), dfs_hld(0);

    for (int i = 0; i < n; ++i) {
        off[head[i]].insert(in[i]);
        answer[i] = 1;
    }

    for (int i = 0; i < m; ++i) {
        int d; cin >> d; --d;

        if (!on[d]) {
            int u = node[d], v = get_root(parent[u]);
            answer[v] += answer[u] - common[u];

            off[head[u]].erase(in[u]);
            on[d] = true;
        } else {
            int u = node[d], v = get_root(u);
            answer[u] = common[u] = answer[v];

            off[head[u]].insert(in[u]);
            on[d] = false;
        }
    }

    for (int i = 0; i < q; ++i) {
        int c; cin >> c; --c;
        cout << answer[get_root(c)] << "\n";
    }
}

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