oj.uz

Submission #478289

# Submission time Handle Problem Language Result Execution time Memory
478289 2021-10-06T19:41:20 Z amunduzbaev Synchronization (JOI13_synchronization) C++14
50 / 100
 271 ms 25540 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){ i++;
		for(;i < N; i += (i & -i)) tree[i] += v;
	}
	
	int get(int i){ 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 3 ms 5068 KB Output is correct
2 Incorrect 3 ms 5068 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 99 ms 22084 KB Output is correct
2 Correct 110 ms 21872 KB Output is correct
3 Correct 105 ms 25008 KB Output is correct
4 Correct 104 ms 24872 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 5068 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 5 ms 5196 KB Output is correct
7 Correct 21 ms 7084 KB Output is correct
8 Correct 271 ms 25132 KB Output is correct
9 Correct 264 ms 25196 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 25180 KB Output is correct
2 Correct 159 ms 25388 KB Output is correct
3 Correct 154 ms 25536 KB Output is correct
4 Correct 152 ms 25540 KB Output is correct

Subtask #5
0 / 40.0

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