oj.uz

Submission #478297

# Submission time Handle Problem Language Result Execution time Memory
478297 2021-10-06T19:48:29 Z amunduzbaev Synchronization (JOI13_synchronization) C++14
100 / 100
 310 ms 23196 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array

const int N = 1e5 + 5;
vector<int> edges[N];
int tin[N], tout[N], t = 1, par[N][20], res[N];

struct BIT{
	int tree[N];
	void add(int i, int v){
		for(++i; i < N; i += (i & -i)) tree[i] += v;
	}
	
	int get(int i){
		int rr = 0;
		for(++i; i; i -= (i & -i)) rr += tree[i];
		return rr;
	}
}tree;

void dfs(int u, int p = -1){
	tin[u] = t++;
	for(int i=1;i<20;i++) par[u][i] = par[par[u][i-1]][i-1];
	for(auto x : edges[u]){
		if(x == p) continue;
		par[x][0] = u, dfs(x, u);
	} tout[u] = t;
	tree.add(tin[u], 1);
	tree.add(tout[u], -1);
}

int find(int x){
	int v = tree.get(tin[x]);
	for(int i=19;~i;i--){
		if(par[x][i] && tree.get(tin[par[x][i]]) == v) x = par[x][i];
	}
	
	return x;
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0); 

	int n, m, q; cin>>n>>m>>q;
	vector<ar<int, 2>> ee(n);
	for(int i=1;i<n;i++){
		cin>>ee[i][0]>>ee[i][1];
		edges[ee[i][0]].push_back(ee[i][1]);
		edges[ee[i][1]].push_back(ee[i][0]);
	}
	
	dfs(1);
	for(int i=1;i<=n;i++) res[i] = 1;
	for(int i=1;i<n;i++){
		if(par[ee[i][0]][0] == ee[i][1]){
			swap(ee[i][0], ee[i][1]);
		}
	}
	vector<int> is(n);
	while(m--){
		int i; cin>>i;
		int par = find(ee[i][0]);
		if(is[i] == -1){
			tree.add(tin[ee[i][1]], 1);
			tree.add(tout[ee[i][1]], -1);
			is[i] = res[ee[i][1]] = res[par];
		} else {
			tree.add(tin[ee[i][1]], -1);
			tree.add(tout[ee[i][1]], 1);
			res[par] += res[ee[i][1]] - is[i];
			is[i] = -1;
		}
	}
	
	while(q--){
		int u; cin>>u;
		cout<<res[find(u)]<<"\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 2 ms 2764 KB Output is correct
7 Correct 13 ms 4084 KB Output is correct
8 Correct 12 ms 4016 KB Output is correct
9 Correct 12 ms 4084 KB Output is correct
10 Correct 174 ms 16468 KB Output is correct
11 Correct 168 ms 16452 KB Output is correct
12 Correct 219 ms 22612 KB Output is correct
13 Correct 82 ms 16700 KB Output is correct
14 Correct 126 ms 16408 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 19672 KB Output is correct
2 Correct 81 ms 19412 KB Output is correct
3 Correct 100 ms 22596 KB Output is correct
4 Correct 99 ms 22596 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2696 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 3 ms 2892 KB Output is correct
7 Correct 18 ms 4688 KB Output is correct
8 Correct 271 ms 22740 KB Output is correct
9 Correct 310 ms 22744 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 22852 KB Output is correct
2 Correct 154 ms 23112 KB Output is correct
3 Correct 145 ms 23108 KB Output is correct
4 Correct 151 ms 23156 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2764 KB Output is correct
6 Correct 17 ms 4044 KB Output is correct
7 Correct 211 ms 16736 KB Output is correct
8 Correct 258 ms 22724 KB Output is correct
9 Correct 108 ms 17268 KB Output is correct
10 Correct 145 ms 17168 KB Output is correct
11 Correct 108 ms 20204 KB Output is correct
12 Correct 131 ms 20196 KB Output is correct
13 Correct 157 ms 23196 KB Output is correct