Submission #824134

#	Time	Username	Problem	Language	Result	Execution time	Memory
824134		Koyote	Synchronization (JOI13_synchronization)	C++14	100 / 100	175 ms	29228 KiB

synchronization

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

typedef pair<int, int> ii;

const int N = 1e5 + 2;
int n, m, q;
int par[N], par_edge[N], subtree_size[N], top_node[N], tin[N], node_id[N];
vector<ii> adj[N];
set<int> roots[N];
int a[N], c[N];
bitset<N> built;

void dfs_init(int u) {
    subtree_size[u] = 1;
    for (auto nei : adj[u]) {
        int v = nei.first, id = nei.second;
        if (v != par[u]) {
            par[v] = u;
            dfs_init(v);
            subtree_size[u] += subtree_size[v];
        } else par_edge[id] = u;
    }
}

void decompose(int u, int top) {
    top_node[u] = top;
    static int timer = 0; tin[u] = timer++;
    node_id[tin[u]] = u;
    roots[top].insert(tin[u]);
    a[u] = 1, c[u] = 0;

    int hv = -1, hsize = 0;
    for (auto nei : adj[u]) {
        int v = nei.first;
        if (v != par[u] && hsize < subtree_size[v]) 
            hv = v, hsize = subtree_size[v];
    }

    if (hv != -1) decompose(hv, top);

    for (auto nei : adj[u]) {
        int v = nei.first;
        if (v != par[u] && v != hv) decompose(v, v);
    }
}

int find_root(int u) {
    while (roots[top_node[u]].upper_bound(tin[u]) == roots[top_node[u]].begin())
        u = par[top_node[u]];
    return node_id[*(--roots[top_node[u]].upper_bound(tin[u]))];
}

void insert_edge(int u) {
    int r = find_root(par[u]);
    a[r] += a[u] - c[u];
    roots[top_node[u]].erase(tin[u]);
}

void delete_edge(int u) {
    int r = find_root(u);
    a[u] = c[u] = a[r];
    roots[top_node[u]].insert(tin[u]);
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m >> q;
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v; u--, v--;
        adj[u].emplace_back(v, i);
        adj[v].emplace_back(u, i);
    }

    par[0] = -1;
    dfs_init(0);
    decompose(0, 0);

    while (m--) {
        int t; cin >> t; t--;
        int u = par_edge[t];
        if (!built[u]) insert_edge(u);
        else delete_edge(u);
        built[u] = !built[u];
    }

    while (q--) {
        int u; cin >> u; u--;
        cout << a[find_root(u)] << '\n';
    }
}

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