Submission #950843

#TimeUsernameProblemLanguageResultExecution timeMemory
950843Ahmed57Synchronization (JOI13_synchronization)C++17
100 / 100
334 ms25032 KiB
#include "bits/stdc++.h" using namespace std; int in[100001],outt[100001]; int P[100001][20]; int bit[100001],dep[100001],ans[100001]; int n;vector<int> adj[100001]; int timer =0 ; void add(int x,int v){ while(x<=n){ bit[x]+=v; x+=x&-x; } } int sum(int x){ int ret = 0; while(x>=1){ ret+=bit[x]; x-=x&-x; } return ret; } void dfs(int x,int pr){ in[x] = ++timer; P[x][0] = pr; dep[x] = dep[pr]+1; for(int j = 1;j<20;j++){ P[x][j] = P[P[x][j-1]][j-1]; } for(auto j:adj[x]){ if(j==pr)continue; dfs(j,x); } outt[x] = timer; } int find(int x){ int no = sum(in[x]); for(int j = 19;j>=0;j--){ if(P[x][j]==0)continue; if(sum(in[P[x][j]])==no){ x = P[x][j]; } } return x; } void se(int x){ add(in[x],1); add(outt[x]+1,-1); } void re(int x){ add(in[x],-1); add(outt[x]+1,1); } signed main() { ios_base::sync_with_stdio(false);cin.tie(0); int m,q;cin>>n>>m>>q; int vis[n] = {0}; int lol[n] = {0}; vector<pair<int,int>> ed; for(int i = 0;i<n-1;i++){ int a,b;cin>>a>>b; adj[a].push_back(b); adj[b].push_back(a); ed.push_back({a,b}); vis[i] = 0; } dfs(1,0); for(int i = 0;i<n-1;i++){ if(dep[ed[i].first]<dep[ed[i].second])swap(ed[i].first,ed[i].second); } for(int i = 1;i<=n;i++){ ans[i] = 1; add(in[i],1); add(outt[i]+1,-1); } for(int i = 0;i<m;i++){ int x;cin>>x;x--; if(vis[x]==0){ int cost = -lol[x]+ans[find(ed[x].second)]+ans[ed[x].first]; re(ed[x].first); ans[find(ed[x].second)] = cost; }else{ lol[x] = ans[find(ed[x].second)]; ans[ed[x].first] = lol[x]; se(ed[x].first); } vis[x] = !vis[x]; } for(int i = 0;i<q;i++){ int x;cin>>x; cout<<ans[find(x)]<<endl; } }
#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...