Submission #1212291

#TimeUsernameProblemLanguageResultExecution timeMemory
1212291minhpkSynchronization (JOI13_synchronization)C++20
0 / 100
626 ms62748 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int a,b,c; vector <int> z[1000005]; int sta[1000005]; int fin[1000005]; int rev[1000005]; int tour; int sz[1000005]; int same[1000005]; int active[1000005]; int par[100005][25]; int f[4000005]; int lazy[4000005]; int high[1000005]; pair<int,int> edge[1000005]; void push(int id){ if (lazy[id]!=0){ lazy[id*2]+=lazy[id]; lazy[id*2+1]+=lazy[id]; f[id*2]+=lazy[id]; f[id*2+1]+=lazy[id]; lazy[id]=0; } } void dfs(int i,int parent){ tour++; sta[i]=tour; rev[tour]=i; par[i][0]=parent; for (auto p:z[i]){ if (p==parent){ continue; } high[p]=high[i]+1; dfs(p,i); } fin[i]=tour; } void build(int id,int l,int r){ if (l==r){ f[id]=high[rev[l]]; return; } int mid=(l+r)/2; build(id*2,l,mid); build(id*2+1,mid+1,r); } void update(int id,int l,int r,int x,int y,int val){ if (x>r || y<l){ return; } if (l>=x && y>=r){ f[id]+=val; lazy[id]+=val; return; } int mid=(l+r)/2; push(id); update(id*2,l,mid,x,y,val); update(id*2+1,mid+1,r,x,y,val); } int get(int id,int l,int r,int pos){ if (l==r){ return f[id]; } int mid=(l+r)/2; push(id); if (pos<=mid){ return get(id*2,l,mid,pos); }else{ return get(id*2+1,mid+1,r,pos); } } int ancestor(int x){ int val=get(1,1,tour,sta[x]); for (int i=20;i>=0;i--){ int nxt=par[x][i]; if (nxt!=0 && get(1,1,tour,sta[nxt])==val){ x=par[x][i]; } } return x; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> a >> b >> c; for (int i=1;i<a;i++){ int x,y; cin >> x >> y; z[x].push_back(y); z[y].push_back(x); edge[i]={x,y}; } tour=0; high[1]=0; dfs(1,0); par[0][0]=0; for (int j=1;j<=20;j++){ for (int i=0;i<=a;i++){ par[i][j]=par[par[i][j-1]][j-1]; } } for (int i=1;i<=a;i++){ sz[i]=1; same[i]=0; active[i]=0; } build(1,1,tour); int q=1; while (b--){ int t; cin >> t; auto [x,y]=edge[t]; if (par[y][0]==x){ swap(x,y); } if (!active[t]){ int anc=ancestor(y); // cout << t << " " << anc << " "; sz[anc]+=sz[x]-same[x]; update(1,1,tour,sta[x],fin[x],-1); // cout << sz[anc] << "\n"; }else{ int anc=ancestor(y); sz[x]=sz[anc]; same[x]=same[anc]; update(1,1,tour,sta[x],fin[x],1); } active[t]=1-active[t]; q++; } while (c--){ int x; cin >> x; int anc=ancestor(x); cout << sz[anc] << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...