oj.uz

Submission #478295

# Submission time Handle Problem Language Result Execution time Memory
478295 2021-10-06T19:47:26 Z amunduzbaev Synchronization (JOI13_synchronization) C++14
100 / 100
 302 ms 28096 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array

const int N = 2e5 + 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 3 ms 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5024 KB Output is correct
6 Correct 5 ms 5200 KB Output is correct
7 Correct 16 ms 6556 KB Output is correct
8 Correct 18 ms 6648 KB Output is correct
9 Correct 15 ms 6608 KB Output is correct
10 Correct 193 ms 21164 KB Output is correct
11 Correct 191 ms 21216 KB Output is correct
12 Correct 246 ms 27448 KB Output is correct
13 Correct 81 ms 21064 KB Output is correct
14 Correct 134 ms 20580 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 22084 KB Output is correct
2 Correct 108 ms 21884 KB Output is correct
3 Correct 108 ms 24944 KB Output is correct
4 Correct 107 ms 25004 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 4 ms 5196 KB Output is correct
7 Correct 21 ms 6988 KB Output is correct
8 Correct 285 ms 25140 KB Output is correct
9 Correct 302 ms 25116 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 25136 KB Output is correct
2 Correct 176 ms 25380 KB Output is correct
3 Correct 163 ms 25540 KB Output is correct
4 Correct 165 ms 25656 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 4 ms 5200 KB Output is correct
6 Correct 19 ms 6696 KB Output is correct
7 Correct 224 ms 21936 KB Output is correct
8 Correct 292 ms 28096 KB Output is correct
9 Correct 111 ms 22108 KB Output is correct
10 Correct 178 ms 21832 KB Output is correct
11 Correct 134 ms 25276 KB Output is correct
12 Correct 121 ms 25280 KB Output is correct
13 Correct 164 ms 27840 KB Output is correct