Submission #171430

#TimeUsernameProblemLanguageResultExecution timeMemory
171430dolphingarlicSynchronization (JOI13_synchronization)C++14
100 / 100
940 ms26232 KiB
#include<bits/stdc++.h> #define F(y)for(int i=1;i<y;i++) #define x first #define y second using namespace std;const int N=3e5;vector<int> g[N];pair<int,int> e[N];int n,m,q,f[N],l[N],t=1,z[N],w[N],c[N][20],b[N];void dfs(int v=1,int p=0){c[v][0]=p;F(20)c[v][i]=c[c[v][i-1]][i-1];f[v]=1;z[v]=t++;for(int i:g[v])if(i!=p)dfs(i,v);w[v]=t;}void up(int p,int val){for(;p<=n;p+=p&(-p))b[p]+=val;}int qu(int p){int ans=0;for(;p;p-=p&(-p))ans+=b[p];return ans;}int lca(int v){int o=v;for(int i=19;~i;i--)if(c[o][i]&&qu(z[c[o][i]])==qu(z[v]))o=c[o][i];return o;}main(){cin>>n>>m>>q;F(n){cin>>e[i].x>>e[i].y;g[e[i].x].push_back(e[i].y);g[e[i].y].push_back(e[i].x);}dfs();F(n+1){up(z[i],-1);up(w[i],1);}while(m--){int x;cin>>x;int u=e[x].x,v=e[x].y;if(c[u][0]==v)swap(u,v);if(lca(v)!=v){f[v]=l[v]=f[lca(u)];up(z[v],-1);up(w[v],1);}else{f[lca(u)]+=f[v]-l[v];up(z[v],1);up(w[v],-1);}}while(q--){int x;cin>>x;cout<<f[lca(x)]<<'\n';}}

Compilation message (stderr)

synchronization.cpp:5:466: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 using namespace std;const int N=3e5;vector<int> g[N];pair<int,int> e[N];int n,m,q,f[N],l[N],t=1,z[N],w[N],c[N][20],b[N];void dfs(int v=1,int p=0){c[v][0]=p;F(20)c[v][i]=c[c[v][i-1]][i-1];f[v]=1;z[v]=t++;for(int i:g[v])if(i!=p)dfs(i,v);w[v]=t;}void up(int p,int val){for(;p<=n;p+=p&(-p))b[p]+=val;}int qu(int p){int ans=0;for(;p;p-=p&(-p))ans+=b[p];return ans;}int lca(int v){int o=v;for(int i=19;~i;i--)if(c[o][i]&&qu(z[c[o][i]])==qu(z[v]))o=c[o][i];return o;}main(){cin>>n>>m>>q;F(n){cin>>e[i].x>>e[i].y;g[e[i].x].push_back(e[i].y);g[e[i].y].push_back(e[i].x);}dfs();F(n+1){up(z[i],-1);up(w[i],1);}while(m--){int x;cin>>x;int u=e[x].x,v=e[x].y;if(c[u][0]==v)swap(u,v);if(lca(v)!=v){f[v]=l[v]=f[lca(u)];up(z[v],-1);up(w[v],1);}else{f[lca(u)]+=f[v]-l[v];up(z[v],1);up(w[v],-1);}}while(q--){int x;cin>>x;cout<<f[lca(x)]<<'\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...