oj.uz

Submission #478280

# Submission time Handle Problem Language Result Execution time Memory
478280 2021-10-06T19:20:07 Z amunduzbaev Synchronization (JOI13_synchronization) C++14
50 / 100
 253 ms 28072 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];
int res[N];

struct BIT{
	int tree[N];
	void add(int i, int v){
		for(;i < N; i += (i & -i)) tree[i] += v;
	}
	
	int get(int i){
		int rr = 0;
		for(;i > 0; 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(tree.get(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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5072 KB Output is correct
2 Incorrect 3 ms 5072 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 24008 KB Output is correct
2 Correct 94 ms 23876 KB Output is correct
3 Correct 98 ms 26748 KB Output is correct
4 Correct 103 ms 26640 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5072 KB Output is correct
2 Correct 3 ms 5072 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 5024 KB Output is correct
6 Correct 5 ms 5200 KB Output is correct
7 Correct 21 ms 7320 KB Output is correct
8 Correct 235 ms 28072 KB Output is correct
9 Correct 235 ms 28016 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 28040 KB Output is correct
2 Correct 157 ms 27672 KB Output is correct
3 Correct 146 ms 27848 KB Output is correct
4 Correct 156 ms 27828 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5028 KB Output is correct
2 Incorrect 3 ms 5072 KB Output isn't correct
3 Halted 0 ms 0 KB -