제출 #1314254

#제출 시각아이디문제언어결과실행 시간메모리
1314254boclobanchat동기화 (JOI13_synchronization)C++20
100 / 100
170 ms21532 KiB
#include<bits/stdc++.h> using namespace std; const int MAXN=1e5+5; int ans[MAXN],pre[MAXN],sp[MAXN][20],fen[MAXN],L[MAXN],R[MAXN],tdfs=0; pair<int,int> edge[MAXN]; vector<int> ds[MAXN]; bool ck[MAXN]; void update(int i,int n,int val) { for(;i<=n;i+=i&-i) fen[i]+=val; } int get(int i) { int ans=0;for(;i;i-=i&-i) ans+=fen[i];return ans; } void dfs(int i,int pre) { sp[i][0]=pre,L[i]=++tdfs; for(int j=1;j<=17;j++) sp[i][j]=sp[sp[i][j-1]][j-1]; for(auto v:ds[i]) if(v!=pre) dfs(v,i); R[i]=tdfs; } int findroot(int pos) { int ans=pos; for(int i=17;i+1;i--) if(get(L[ans])-get(L[sp[ans][i]])==(1<<i)) ans=sp[ans][i]; return ans; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m,q; cin>>n>>m>>q; for(int i=1;i<n;i++) { int l,r; cin>>l>>r; ds[l].push_back(r),ds[r].push_back(l),edge[i]={l,r}; } dfs(1,1); for(int i=1;i<=n;i++) ans[i]=1; for(int i=1;i<=m;i++) { int pos; cin>>pos; ck[pos]=1-ck[pos]; int l=edge[pos].first,r=edge[pos].second; if(sp[l][0]!=r) swap(l,r); if(ck[pos]) { update(L[l],n,1); update(R[l]+1,n,-1); ans[findroot(l)]+=ans[l]-pre[l]; } else { pre[l]=ans[l]=ans[findroot(l)]; update(L[l],n,-1); update(R[l]+1,n,1); } } while(q--) { int res; cin>>res; cout<<ans[findroot(res)]<<"\n"; } }
#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...