답안 #171430

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
171430 2019-12-28T16:18:42 Z dolphingarlic 동기화 (JOI13_synchronization) C++14
100 / 100
940 ms 26232 KB
#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

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';}}
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  ^
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 9 ms 7416 KB Output is correct
4 Correct 8 ms 7416 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 10 ms 7544 KB Output is correct
7 Correct 39 ms 8824 KB Output is correct
8 Correct 39 ms 8824 KB Output is correct
9 Correct 39 ms 8824 KB Output is correct
10 Correct 484 ms 21212 KB Output is correct
11 Correct 491 ms 21276 KB Output is correct
12 Correct 607 ms 25856 KB Output is correct
13 Correct 342 ms 21632 KB Output is correct
14 Correct 334 ms 20956 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 306 ms 23448 KB Output is correct
2 Correct 307 ms 23168 KB Output is correct
3 Correct 284 ms 25508 KB Output is correct
4 Correct 288 ms 25528 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 9 ms 7416 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct
6 Correct 15 ms 7544 KB Output is correct
7 Correct 79 ms 9336 KB Output is correct
8 Correct 940 ms 26132 KB Output is correct
9 Correct 936 ms 25976 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 921 ms 25976 KB Output is correct
2 Correct 659 ms 25948 KB Output is correct
3 Correct 651 ms 26204 KB Output is correct
4 Correct 651 ms 26104 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 8 ms 7416 KB Output is correct
4 Correct 9 ms 7420 KB Output is correct
5 Correct 14 ms 7544 KB Output is correct
6 Correct 73 ms 8824 KB Output is correct
7 Correct 861 ms 21616 KB Output is correct
8 Correct 934 ms 25956 KB Output is correct
9 Correct 622 ms 22128 KB Output is correct
10 Correct 700 ms 21748 KB Output is correct
11 Correct 639 ms 24184 KB Output is correct
12 Correct 644 ms 24104 KB Output is correct
13 Correct 676 ms 26232 KB Output is correct