oj.uz

Submission #171426

# Submission time Handle Problem Language Result Execution time Memory
171426 2019-12-28T16:12:02 Z dolphingarlic Synchronization (JOI13_synchronization) C++14
100 / 100
 984 ms 23928 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=200001;
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

synchronization.cpp:29:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 7 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 9 ms 5240 KB Output is correct
7 Correct 37 ms 6392 KB Output is correct
8 Correct 42 ms 6520 KB Output is correct
9 Correct 40 ms 6520 KB Output is correct
10 Correct 485 ms 18928 KB Output is correct
11 Correct 505 ms 18936 KB Output is correct
12 Correct 574 ms 23516 KB Output is correct
13 Correct 327 ms 19204 KB Output is correct
14 Correct 340 ms 18552 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 21112 KB Output is correct
2 Correct 302 ms 20816 KB Output is correct
3 Correct 282 ms 23196 KB Output is correct
4 Correct 282 ms 23288 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 7 ms 4984 KB Output is correct
6 Correct 12 ms 5240 KB Output is correct
7 Correct 76 ms 6904 KB Output is correct
8 Correct 935 ms 23788 KB Output is correct
9 Correct 949 ms 23876 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 975 ms 23712 KB Output is correct
2 Correct 671 ms 23700 KB Output is correct
3 Correct 665 ms 23896 KB Output is correct
4 Correct 684 ms 23928 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 4988 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 12 ms 5240 KB Output is correct
6 Correct 71 ms 6504 KB Output is correct
7 Correct 863 ms 19416 KB Output is correct
8 Correct 984 ms 23800 KB Output is correct
9 Correct 622 ms 19828 KB Output is correct
10 Correct 673 ms 19252 KB Output is correct
11 Correct 634 ms 21804 KB Output is correct
12 Correct 633 ms 21896 KB Output is correct
13 Correct 647 ms 23928 KB Output is correct