제출 #1178763

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1178763		AlgorithmWarrior	동기화 (JOI13_synchronization)	C++20	100 / 100	283 ms	23064 KiB

synchronization

#include <bits/stdc++.h>

using namespace std;

int const LOG=20;
int const MAX=100005;
vector<int>tree[MAX];
int n,m,q;
int x[MAX],y[MAX];
int tin[MAX],tout[MAX];
int lift[MAX][LOG];
int cardN[MAX],cardM[MAX];
bool activ[MAX];

int ub(int x){
    return x&(-x);
}

struct AIB{
    int v[MAX];
    void add(int pos,int val){
        while(pos<=n){
            v[pos]+=val;
            pos+=ub(pos);
        }
    }
    int sum(int pos){
        int s=0;
        while(pos){
            s+=v[pos];
            pos-=ub(pos);
        }
        return s;
    }
}aib;

void read(){
    cin>>n>>m>>q;
    int i;
    for(i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        tree[u].push_back(v);
        tree[v].push_back(u);
        x[i]=u;
        y[i]=v;
    }
}

void dfs(int nod){
    int i;
    for(i=1;i<LOG;++i)
        lift[nod][i]=lift[lift[nod][i-1]][i-1];
    static int time=0;
    tin[nod]=++time;
    for(auto fiu : tree[nod])
        if(fiu!=lift[nod][0]){
            lift[fiu][0]=nod;
            dfs(fiu);
        }
    tout[nod]=time;
}

void init(){
    int i;
    for(i=1;i<=n;++i)
        cardN[i]=1;
    for(i=1;i<n;++i)
        if(lift[x[i]][0]==y[i])
            swap(x[i],y[i]);
    for(i=1;i<=n;++i){
        aib.add(tin[i],1);
        aib.add(tout[i]+1,-1);
    }
}

int rad(int nod){
    int i;
    for(i=LOG-1;i>=0;--i)
        if(aib.sum(tin[nod])==aib.sum(tin[lift[nod][i]]))
            nod=lift[nod][i];
    return nod;
}

void process_changes(){
    int i;
    for(i=1;i<=m;++i){
        int id;
        cin>>id;
        if(activ[id]){
            int root=rad(y[id]);
            cardN[y[id]]=cardN[root];
            cardM[id]=cardN[root];
            aib.add(tin[y[id]],1);
            aib.add(tout[y[id]]+1,-1);
            activ[id]=0;
        }
        else{
            aib.add(tin[y[id]],-1);
            aib.add(tout[y[id]]+1,1);
            int root=rad(y[id]);
            cardN[root]+=cardN[y[id]]-cardM[id];
            activ[id]=1;
        }
    }
}

void process_queries(){
    int i;
    for(i=1;i<=q;++i){
        int qry;
        cin>>qry;
        int root=rad(qry);
        cout<<cardN[root]<<'\n';
    }
}

int main()
{
    read();
    dfs(1);
    init();
    process_changes();
    process_queries();
    return 0;
}

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