Submission #859900

#	Time	Username	Problem	Language	Result	Execution time	Memory
859900		TS_2392	Synchronization (JOI13_synchronization)	C++14	100 / 100	213 ms	25288 KiB

synchronization

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define dbg(x) cout << #x << " = " << (x) << ' '
using namespace std;
const int N = 1e5 + 3;
int n, m, q, tin[N], tout[N], timer;
int jmp[N][17], bit[2 * N], f[N], last_del[N];
bool stat[N];
vector<int> adj[N];
pair<int, int> edge[N];
void dfs(int u, int par){
    tin[u] = ++timer;
    for(int &v : adj[u]) if(v != par){
        jmp[v][0] = u;
        for(int i = 1; i < 17; ++i) if(jmp[v][i - 1]){
            jmp[v][i] = jmp[jmp[v][i - 1]][i - 1];
        }
        dfs(v, u);
    }
    tout[u] = ++timer;
}
void update(int i, int v){
    for(; i <= timer; i += i & -i) bit[i] += v;
}
int query(int i){
    int res = 0;
    for(; i >= 1; i -= i & -i) res += bit[i];
    return res;
}
int get_root(int node) {
    int lca = node;
    for (int i = 16; ~i; i--) {
        if (jmp[lca][i] && query(tin[jmp[lca][i]]) == query(tin[node])) lca = jmp[lca][i];
    }
    return lca;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m >> q;
    for(int i = 1; i < n; ++i){
        cin >> edge[i].fi >> edge[i].se;
        adj[edge[i].fi].eb(edge[i].se);
        adj[edge[i].se].eb(edge[i].fi);
    }
    dfs(1, 0);
    for(int i = 1; i < n; ++i){
        if(jmp[edge[i].fi][0] == edge[i].se) swap(edge[i].fi, edge[i].se);
    }
    for(int i = 1; i <= n; ++i){
        f[i] = 1;
        update(tin[i], -1);
        update(tout[i], 1);
    }
    while(m--){
        int id, u, v, root_u; cin >> id;
        tie(u, v) = edge[id]; root_u = get_root(u);
        if(stat[id] == 0){
            f[root_u] = f[root_u] + f[v] - last_del[v];
            update(tin[v], 1); update(tout[v], -1);
        }
        else{
            last_del[v] = f[v] = f[root_u];
            update(tin[v], -1); update(tout[v], 1);
        }
        stat[id] = !stat[id];
    }
    while(q--){
        int u; cin >> u;
        cout << f[get_root(u)] << '\n';
    }
    return 0;
}

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