Submission #824386

#	Time	Username	Problem	Language	Result	Execution time	Memory
824386		Koyote	Synchronization (JOI13_synchronization)	C++14	100 / 100	184 ms	29268 KiB

synchronization

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

const int N = 1e5 + 2;
int n, m, q, a[N], c[N];
int par[N], top_node[N], tin[N], subtree_size[N], node_from_time[N], tail_edge[N];
vector<pair<int, int>> adj[N];
set<int> children[N];
bitset<N> built;

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

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

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

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

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

void remove_edge(int u) {
    int r = find_root(u);
    a[u] = c[u] = a[r];
    children[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 = tail_edge[t];
        if (!built[u]) insert_edge(u);
        else remove_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