Submission #618144

#	Time	Username	Problem	Language	Result	Execution time	Memory
618144		czhang2718	Synchronization (JOI13_synchronization)	C++17	100 / 100	276 ms	27468 KiB

synchronization

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

const int N=1e5+1, K=18;
int n, m, q, t;
vector<int> adj[N];
int par[N][K];
int h[N];
int tin[N], tout[N];
int a[N], b[N];
int edge[N][2];
bool on[N];

void dfs(int x){
    tin[x]=++t;
    for(int i=1; i<K; i++){
        par[x][i]=par[par[x][i-1]][i-1];
    }
    for(int k:adj[x]){
        if(k==par[x][0]) continue;
        par[k][0]=x;
        h[k]=h[x]+1;
        dfs(k);
    }
    tout[x]=++t;
}

int sum[2*N];

int qry(int i){
    int ret=0;
    while(i){
        ret+=sum[i];
        i-=i&-i;
    }
    return ret;
}

void upd(int i, int v){
    while(i<=2*n){
        sum[i]+=v;
        i+=i&-i;
    }
}

void upd(int l, int r, int v){
    upd(l, v);
    upd(r+1, -v);
}

int getrt(int x){
    int u=x;
    int c=qry(tin[x]);
    for(int k=K-1; k>=0; k--){
        if(par[u][k] && c-qry(tin[par[u][k]])==h[x]-h[par[u][k]]) u=par[u][k]; 
    }
    return u;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m >> q;
    for(int i=1; i<n; i++){
        int u,v; cin >> u >> v;
        edge[i][0]=u;
        edge[i][1]=v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1);

    for(int i=1; i<=n; i++) a[i]=1;

    while(m--){
        int e; cin >> e;
        int u=edge[e][0], v=edge[e][1];
        if(h[u]>h[v]) swap(u,v);
        // u
        // v
        int rt=getrt(u);
        // cout << "uvroot " << u << " " << v << " " << rt << "\n";
        if(on[e]){
            b[e]=a[rt];
            a[v]=a[rt];
            upd(tin[v], tout[v], -1);
        }
        else{
            a[rt]=a[rt]+a[v]-b[e];
            upd(tin[v], tout[v], 1);
        }
        // cout << "a[" << rt << "] = " << a[rt] << "\n";
        on[e]=!on[e];
    }

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

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