Submission #1287569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287569		nguyenkhangninh99	Synchronization (JOI13_synchronization)	C++20	100 / 100	562 ms	31080 KiB

synchronization

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

#define int long long

const int maxn = 1e5 + 5, LG = 18;
int up[LG][maxn], tin[maxn], out[maxn], timedfs;
vector<int> g[maxn];
void dfs(int u){
    tin[u] = ++timedfs;
    for(int v: g[u]){
        if(v == up[0][u]) continue;
        up[0][v] = u;
        for(int i = 1; i < LG; i++) up[i][v] = up[i - 1][up[i - 1][v]];
        dfs(v);
    }
    out[u] = timedfs;
}

int state[maxn], bit[maxn], last[maxn];
void update(int p, int val){
    for(; p < maxn; p += p & -p) bit[p] += val;
}
int get(int p){
    int res = 0;
    for(; p; p -= p & -p) res += bit[p];
    return res;
}
int root(int u){
    for(int i = LG - 1; i >= 0; i--){
        if(up[i][u] == 0) continue;
        if(get(tin[u]) - get(tin[up[i][u]]) == 0) u = up[i][u];
    }
    return u;
}
signed main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    
    int n, m, q; cin >> n >> m >> q;

    vector<pair<int, int>> edge(n + 1);
    for(int i = 2; i <= n; i++){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        edge[i] = {u, v};
    }

    dfs(1);
    
    for(int i = 2; i <= n; i++){
        if(edge[i].second == up[0][edge[i].first]) swap(edge[i].first, edge[i].second);
        update(tin[i], 1);
        update(out[i] + 1, -1);
    }

    vector<int> ans(n + 1,1);
    while(m--){
        int i; cin >> i;
        i++;
        state[i] ^= 1;
        int u = edge[i].first, v = edge[i].second;
        if(state[i] == 1){
            update(tin[v], -1);
            update(out[v] + 1, 1);
            ans[root(u)] += ans[v] - last[v];
        }else{
            update(tin[v], 1);
            update(out[v] + 1, -1);
            last[v] = ans[v] = ans[root(u)];
        }
    }

    while(q--){
        int x;
        cin >> x;
        cout << ans[root(x)] << "\n";
    }

    return 0;
}

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