| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 171429 | 2019-12-28T16:15:20 Z | dolphingarlic | Synchronization (JOI13_synchronization) | C++14 | 952 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,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
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 11 ms | 7416 KB | Output is correct |
| 2 | Correct | 9 ms | 7416 KB | Output is correct |
| 3 | Correct | 8 ms | 7416 KB | Output is correct |
| 4 | Correct | 9 ms | 7416 KB | Output is correct |
| 5 | Correct | 10 ms | 7416 KB | Output is correct |
| 6 | Correct | 10 ms | 7544 KB | Output is correct |
| 7 | Correct | 40 ms | 8820 KB | Output is correct |
| 8 | Correct | 39 ms | 8824 KB | Output is correct |
| 9 | Correct | 39 ms | 8696 KB | Output is correct |
| 10 | Correct | 522 ms | 21368 KB | Output is correct |
| 11 | Correct | 540 ms | 21308 KB | Output is correct |
| 12 | Correct | 573 ms | 25820 KB | Output is correct |
| 13 | Correct | 327 ms | 21596 KB | Output is correct |
| 14 | Correct | 336 ms | 20856 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 308 ms | 23472 KB | Output is correct |
| 2 | Correct | 295 ms | 23160 KB | Output is correct |
| 3 | Correct | 284 ms | 25464 KB | Output is correct |
| 4 | Correct | 286 ms | 25516 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 10 ms | 7416 KB | Output is correct |
| 2 | Correct | 8 ms | 7420 KB | Output is correct |
| 3 | Correct | 11 ms | 7544 KB | Output is correct |
| 4 | Correct | 10 ms | 7416 KB | Output is correct |
| 5 | Correct | 10 ms | 7416 KB | Output is correct |
| 6 | Correct | 15 ms | 7544 KB | Output is correct |
| 7 | Correct | 81 ms | 9312 KB | Output is correct |
| 8 | Correct | 932 ms | 25992 KB | Output is correct |
| 9 | Correct | 933 ms | 26104 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 942 ms | 26196 KB | Output is correct |
| 2 | Correct | 647 ms | 25976 KB | Output is correct |
| 3 | Correct | 654 ms | 26232 KB | Output is correct |
| 4 | Correct | 658 ms | 26232 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 9 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 | 7416 KB | Output is correct |
| 5 | Correct | 14 ms | 7516 KB | Output is correct |
| 6 | Correct | 76 ms | 8824 KB | Output is correct |
| 7 | Correct | 872 ms | 21656 KB | Output is correct |
| 8 | Correct | 952 ms | 26064 KB | Output is correct |
| 9 | Correct | 627 ms | 22184 KB | Output is correct |
| 10 | Correct | 708 ms | 21652 KB | Output is correct |
| 11 | Correct | 643 ms | 24136 KB | Output is correct |
| 12 | Correct | 631 ms | 24056 KB | Output is correct |
| 13 | Correct | 651 ms | 26232 KB | Output is correct |