Submission #1107481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107481		doducanh	Synchronization (JOI13_synchronization)	C++14	30 / 100	185 ms	25216 KiB

synchronization

///breaker
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<int,int>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
const int maxn=1e5+7;
int lc[maxn];
int x[maxn],y[maxn];
int in[maxn],out[maxn];
vector<int>adj[maxn];
int t[maxn];
int p[25][maxn];
int v[maxn];
int n,m,q;
int cnt=0;
int get(int x)
{
    int res=0;
    for(;x;x-=(x&(-x)))res+=t[x];
    return res;
}
void add(int x,int val)
{
    for(;x<maxn;x+=(x&(-x)))t[x]+=val;
}
void dfs(int u,int par)
{
    in[u]=++cnt;
    for(int v:adj[u])if(v!=par){
        p[0][v]=u;
        dfs(v,u);
    }
    out[u]=cnt;
}
int Find(int x)
{
    int u=x;
    int tmp=get(in[u]);
    for(int i=20;i>=0;i--)if(p[i][u]!=0&&get(in[p[i][u]])==tmp){
        u=p[i][u];
    }
    return u;
}
void sol(void){
    cin>>n>>m>>q;
    for(int i=1;i<n;i++){
        lc[i]=0;
        cin>>x[i]>>y[i];
        adj[x[i]].push_back(y[i]);
        adj[y[i]].push_back(x[i]);
    }
    dfs(1,0);
    for(int i=1;i<=20;i++){
        for(int j=1;j<=n;j++){
            p[i][j]=p[i-1][p[i-1][j]];
        }
    }
    for(int i=1;i<=n;i++){
        v[i]=1;
        add(in[i],1);
    }
    for(int i=1;i<n;i++){
        if(p[0][x[i]]==y[i])swap(x[i],y[i]);
    }
    for(int i=1;i<=m;i++){
        int j;
        cin>>j;
        int xj=Find(x[j]);
        if(lc[j]==-1){
            add(in[y[j]],1);
            lc[j]=v[y[j]]=v[xj];
        }
        else{
            add(in[y[j]],-1);
            v[xj]+=(v[y[j]]-lc[j]);
            lc[j]=-1;
        }
    }
    while(q--){
        int x;
        cin>>x;
        cout<<v[Find(x)]<<"\n";
    }
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    while(t--){
        sol();
    }
    // you should actually read the stuff at the bottom
    return 0;
}
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

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