Submission #171429

#TimeUsernameProblemLanguageResultExecution timeMemory
171429dolphingarlicSynchronization (JOI13_synchronization)C++14
100 / 100
952 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,tin[N],tout[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;tin[v]=t++;for(int i:g[v])if(i != p)dfs(i,v);tout[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 ll=v;for(int i=19;~i;i--)if(c[ll][i]&&qu(tin[c[ll][i]])==qu(tin[v]))ll=c[ll][i];return ll;}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(tin[i],-1);up(tout[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(tin[v],-1);up(tout[v],1);}else{f[lca(u)] += f[v]-l[v];up(tin[v],1);up(tout[v],-1);}}while(q--){int x;cin>>x;cout<<f[lca(x)]<<'\n';}}

Compilation message (stderr)

synchronization.cpp:5:506: 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,tin[N],tout[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;tin[v]=t++;for(int i:g[v])if(i != p)dfs(i,v);tout[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 ll=v;for(int i=19;~i;i--)if(c[ll][i]&&qu(tin[c[ll][i]])==qu(tin[v]))ll=c[ll][i];return ll;}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(tin[i],-1);up(tout[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(tin[v],-1);up(tout[v],1);}else{f[lca(u)] += f[v]-l[v];up(tin[v],1);up(tout[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...