| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 171430 | 2019-12-28T16:18:42 Z | dolphingarlic | Synchronization (JOI13_synchronization) | C++14 | 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
| # | Verdict | Execution time | Memory | 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 |
| # | Verdict | Execution time | Memory | 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 |
| # | Verdict | Execution time | Memory | 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 |
| # | Verdict | Execution time | Memory | 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 |
| # | Verdict | Execution time | Memory | 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 |