Submission #480705

#	Time	Username	Problem	Language	Result	Execution time	Memory
480705		SirCovidThe19th	Synchronization (JOI13_synchronization)	C++17	100 / 100	620 ms	24572 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;
 
const int mx = 1e5 + 5, ml = 17;
 
int n, m, q, vals[mx], ans[mx], bit[mx], up[mx][ml], tin[mx], tout[mx], ti; 
 
bool on[mx]; vector<int> adj[mx]; vector<pair<int, int>> edg;
 
void dfs(int u){
    tin[u] = ++ti;
    for (int l = 1; l < ml; l++) up[u][l] = up[up[u][l - 1]][l - 1];
    for (int v : adj[u]) if (v != up[u][0]) up[v][0] = u, dfs(v);
    tout[u] = ti;
}
void upd(int l, int r, int v){
    for (; l <= n; l += l & (-l)) bit[l] += v;
    for (r++; r <= n; r += r & (-r)) bit[r] -= v;
}
int qry(int i){
    int ret = 0;
	for(;i; i -= i & (-i)) ret += bit[i];
	return ret;
}
int par(int i){
    for (int l = ml - 1; ~l; l--){
        int anc = up[i][l];
        if (anc and qry(tin[i]) == qry(tin[anc])) i = anc;
    }
    return i;
}
 
int main(){
    cin >> n >> m >> q; edg.resize(n);
    for (int i = 1; i < n; i++){
        int a, b; cin >> a >> b; 
        adj[a].push_back(b); adj[b].push_back(a);
        edg[i] = {a, b};
    }
 
    dfs(1);
    for (int i = 1; i <= n; i++) vals[i] = ans[i] = 1, upd(tin[i], tout[i], 1);
 
    while (m--){
        int op, u, v; cin >> op; u = edg[op].first, v = edg[op].second; 
        if (u != up[v][0]) swap(u, v); //u up, v down
      
        if (!on[op]){
            u = par(u); 
            vals[u] += vals[v]; ans[u] += vals[v];
            vals[v] = 0; ans[v] = 0;
            upd(tin[v], tout[v], -1);
        }
        else{
            ans[v] = ans[par(u)];
            upd(tin[v], tout[v], 1); 
        }
        on[op] = !on[op];
    }
    while (q--){
        int ask; cin >> ask;
        cout<<ans[par(ask)]<<endl;
    }
}

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