Submission #231409

#TimeUsernameProblemLanguageResultExecution timeMemory
231409thebesSynchronization (JOI13_synchronization)C++14
100 / 100
910 ms28024 KiB
#include <bits/stdc++.h> using namespace std; const int MN = 1e5+5, LG = 19; int st[3*MN], lz[3*MN], sp[MN][LG], N, M, Q, i, x, y, dep[MN], vis[MN][2], lst[MN], nxt, sz[MN], on[MN]; pair<int,int> e[MN]; vector<int> adj[MN]; inline void upd_lz(int i,int s,int e){ st[i] += lz[i]; if(s!=e){ lz[2*i] += lz[i]; lz[2*i+1] += lz[i]; } lz[i] = 0; } void upd(int i,int s,int e,int ss,int se,int v){ upd_lz(i, s, e); if(s>=ss&&e<=se){lz[i]=v; upd_lz(i,s,e);} else{ if((s+e)/2<ss) upd(2*i+1,(s+e)/2+1,e,ss,se,v),upd_lz(2*i,s,(s+e)/2); else if((s+e)/2>=se) upd(2*i,s,(s+e)/2,ss,se,v),upd_lz(2*i+1,(s+e)/2+1,e); else upd(2*i,s,(s+e)/2,ss,se,v),upd(2*i+1,(s+e)/2+1,e,ss,se,v); st[i]=st[2*i]+st[2*i+1]; } } int qu(int i,int s,int e,int idx){ upd_lz(i,s,e); if(s==e) return st[i]; else if((s+e)/2<idx) return qu(2*i+1,(s+e)/2+1,e,idx); else return qu(2*i,s,(s+e)/2,idx); } void dfs(int n,int p,int d){ vis[n][0] = ++nxt; sp[n][0]=p; dep[n]=d; for(auto v : adj[n]){ if(v==p) continue; dfs(v,n,d+1); } vis[n][1] = nxt; } int anc(int n){ int val = qu(1,1,N,vis[n][0]); for(int i=LG-1;i>=0;i--){ if(sp[n][i]){ int nn = sp[n][i]; if(qu(1,1,N,vis[nn][0])==val) n = nn; } } return n; } int main(){ for(scanf("%d%d%d",&N,&M,&Q),i=1;i<N;i++){ scanf("%d%d",&x,&y); adj[x].push_back(y); adj[y].push_back(x); e[i]={x,y}; } dfs(1,0,1); for(int j=1;j<LG;j++){ for(i=1;i<=N;i++) sp[i][j]=sp[sp[i][j-1]][j-1]; } for(i=1;i<N;i++){ if(dep[e[i].first]>dep[e[i].second]) swap(e[i].first,e[i].second); } for(i=2;i<=N;i++) upd(1,1,N,vis[i][0],vis[i][1],1); for(i=1;i<=N;i++) sz[i]=1; for(i=1;i<=M;i++){ scanf("%d",&x); int p=e[x].first, c=e[x].second; if(on[x]){ int rt = anc(c); lst[x] = sz[c] = sz[rt]; upd(1,1,N,vis[c][0],vis[c][1],1); } else{ upd(1,1,N,vis[c][0],vis[c][1],-1); int rt = anc(c); sz[rt] += sz[c]-lst[x]; } on[x]=!on[x]; } for(i=1;i<=Q;i++){ scanf("%d",&x); printf("%d\n",sz[anc(x)]); } return 0; }

Compilation message (stderr)

synchronization.cpp: In function 'int main()':
synchronization.cpp:78:13: warning: unused variable 'p' [-Wunused-variable]
         int p=e[x].first, c=e[x].second;
             ^
synchronization.cpp:59:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%d%d%d",&N,&M,&Q),i=1;i<N;i++){
         ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
synchronization.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
         ~~~~~^~~~~~~~~~~~~~
synchronization.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
         ~~~~~^~~~~~~~~
synchronization.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
         ~~~~~^~~~~~~~~
#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...