oj.uz

Submission #379432

# Submission time Handle Problem Language Result Execution time Memory
379432 2021-03-18T08:57:10 Z reymontada61 Synchronization (JOI13_synchronization) C++14
100 / 100
 2577 ms 28268 KB 
#include <bits/stdc++.h>
using namespace std;

int n, m, q;
const int MXN = 100005, MXK = 20;
vector<int> adj[MXN];

int par[MXN][MXK];

int eda[MXN], edb[MXN];
int depth[MXN];
int st_start[MXN], st_end[MXN];

int ti = 1;

void dfs(int node, int pa, int dep) {
	depth[node] = dep;
	par[node][0] = pa;
	st_start[node] = ti;
	ti++;
	for (int i=1; i<MXK; i++) {
		par[node][i] = par[par[node][i-1]][i-1];
	}
	for (auto x: adj[node]) {
		if (x == pa) continue;
		dfs(x, node, dep+1);
	}
	st_end[node] = ti;
	ti++;
}

int seg[MXN * 8];

void add(int ind, int l, int r, int pos, int by) {
	if (l == r) {
		seg[ind] += by;
		return;
	}
	int m = (l + r) / 2;
	if (pos <= m) add(ind*2, l, m, pos, by);
	else add(ind*2+1, m+1, r, pos, by);
	seg[ind] = seg[ind*2] + seg[ind*2+1];
}

int query(int ind, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr) return seg[ind];
	if (ql > r || qr < l) return 0;
	int m = (l + r) / 2;
	return query(ind*2, l, m, ql, qr) + query(ind*2+1, m+1, r, ql, qr);
}

int kth(int n, int k) {
	for (int i=0; i<MXK; i++) {
		if (k & (1 << i)) n = par[n][i];
	}
	return n;
}

int path(int x, int y) {
	return query(1, 1, 2*n, 1, st_start[y]) - query(1, 1, 2*n, 1, st_start[x]);
}

int truepar(int x) {
	int ans = x;
	for (int i=MXK-1; i>=0; i--) {
		if (path(par[ans][i], x) == (depth[x] - depth[par[ans][i]])) {
			ans = par[ans][i];
		}
	}
	return ans;
}

bool built[MXN];
int ans[MXN], c[MXN];

signed main() {

	cin >> n >> m >> q;
	for (int i=1; i<=n-1; i++) {
		int a, b;
		cin >> a >> b;
		eda[i] = a;
		edb[i] = b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for (int i=1; i<=n; i++) {
		ans[i] = 1;
	}
	
	for (int i=0; i<MXN; i++) for (int j=0; j<MXK; j++) par[i][j] = 1;
	
	dfs(1, 1, 0);
	
	while (m--) {
		int x;
		cin >> x;
		
		int a = eda[x], b = edb[x];
		if (depth[a] > depth[b]) swap(a, b);
		
		if (built[x]) {
			ans[b] = c[b] = ans[truepar(a)];
			add(1, 1, 2*n, st_start[b], -1);
			add(1, 1, 2*n, st_end[b], 1);
		}
		else {
			ans[truepar(a)] += ans[b] - c[b];
			add(1, 1, 2*n, st_start[b], 1);
			add(1, 1, 2*n, st_end[b], -1);
		}
		built[x] = !built[x];
		
		
	}
	
	while (q--) {
		int j;
		cin >> j;
		cout << ans[truepar(j)] << endl;
	}

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10604 KB Output is correct
2 Correct 7 ms 10604 KB Output is correct
3 Correct 7 ms 10624 KB Output is correct
4 Correct 7 ms 10616 KB Output is correct
5 Correct 8 ms 10604 KB Output is correct
6 Correct 15 ms 10604 KB Output is correct
7 Correct 119 ms 11756 KB Output is correct
8 Correct 118 ms 11628 KB Output is correct
9 Correct 117 ms 11628 KB Output is correct
10 Correct 1552 ms 20972 KB Output is correct
11 Correct 1545 ms 21100 KB Output is correct
12 Correct 1692 ms 27244 KB Output is correct
13 Correct 1392 ms 20968 KB Output is correct
14 Correct 818 ms 19948 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1159 ms 23788 KB Output is correct
2 Correct 1159 ms 23424 KB Output is correct
3 Correct 728 ms 26340 KB Output is correct
4 Correct 726 ms 26236 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10604 KB Output is correct
2 Correct 7 ms 10604 KB Output is correct
3 Correct 8 ms 10604 KB Output is correct
4 Correct 10 ms 10604 KB Output is correct
5 Correct 8 ms 10604 KB Output is correct
6 Correct 27 ms 10732 KB Output is correct
7 Correct 199 ms 12304 KB Output is correct
8 Correct 2544 ms 28268 KB Output is correct
9 Correct 2543 ms 27888 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2577 ms 27884 KB Output is correct
2 Correct 1544 ms 27376 KB Output is correct
3 Correct 1552 ms 27620 KB Output is correct
4 Correct 1523 ms 27372 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10604 KB Output is correct
2 Correct 7 ms 10604 KB Output is correct
3 Correct 9 ms 10604 KB Output is correct
4 Correct 9 ms 10604 KB Output is correct
5 Correct 25 ms 10604 KB Output is correct
6 Correct 192 ms 11628 KB Output is correct
7 Correct 2504 ms 21868 KB Output is correct
8 Correct 2562 ms 28012 KB Output is correct
9 Correct 2139 ms 22028 KB Output is correct
10 Correct 1692 ms 21228 KB Output is correct
11 Correct 1957 ms 24880 KB Output is correct
12 Correct 1959 ms 24812 KB Output is correct
13 Correct 1576 ms 27556 KB Output is correct