oj.uz

Submission #33189

# Submission time Handle Problem Language Result Execution time Memory
33189 2017-10-22T12:56:07 Z aome Synchronization (JOI13_synchronization) C++14
100 / 100
 546 ms 16908 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int n, m, q;
int cnt;
int res[N], lst[N];
int h[N], st[N], ed[N], pos[N];
int from[N], to[N];
int it[4 * N];
bool type[N];
vector<int> G[N];

void dfs(int u, int p) {
	st[u] = ++cnt, pos[cnt] = u;
	for (auto v : G[u]) {
		if (v == p) continue;
		h[v] = h[u] + 1, dfs(v, u);
	}
	ed[u] = cnt;
}

void build(int i, int l, int r) {
	if (l == r) {
		it[i] = ed[pos[l]]; return;
	}
	int mid = (l + r) >> 1;
	build(i << 1, l, mid), build(i << 1 | 1, mid + 1, r);
	it[i] = max(it[i << 1], it[i << 1 | 1]);
}

void upd(int i, int l, int r, int p, int x) {
	if (l == r) {
		it[i] = x; return;
	}
	int mid = (l + r) >> 1;
	if (mid >= p) upd(i << 1, l, mid, p, x);
	else upd(i << 1 | 1, mid + 1, r, p, x);
	it[i] = max(it[i << 1], it[i << 1 | 1]);
}

int find(int i, int l, int r, int u, int v) {
	if (l > u || it[i] < v) return -1;
	if (l == r) return l;
	int mid = (l + r) >> 1;
	int res = find(i << 1 | 1, mid + 1, r, u, v);
	if (res != -1) return res;
	return find(i << 1, l, mid, u, v);
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> q;
	for (int i = 1; i < n; ++i) {
		cin >> from[i] >> to[i];
		G[from[i]].push_back(to[i]);
		G[to[i]].push_back(from[i]);
	}
	dfs(1, 1);
	for (int i = 1; i <= n; ++i) res[i] = 1;
	build(1, 1, n);
	for (int i = 1; i < n; ++i) {
		if (h[from[i]] > h[to[i]]) swap(from[i], to[i]);
	}
	for (int i = 1; i <= m; ++i) {
		int x; cin >> x;
		if (!type[x]) {
			res[pos[find(1, 1, n, st[from[x]], ed[from[x]])]] += res[to[x]] - lst[x];
			upd(1, 1, n, st[to[x]], 0);
		}
		else {
			res[to[x]] = lst[x] = res[pos[find(1, 1, n, st[from[x]], ed[from[x]])]];
			upd(1, 1, n, st[to[x]], ed[to[x]]);
		}
		type[x] ^= 1;
	}
	for (int i = 1; i <= q; ++i) {
		int x; cin >> x; cout << res[pos[find(1, 1, n, st[x], ed[x])]] << '\n';
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9304 KB Output is correct
2 Correct 0 ms 9304 KB Output is correct
3 Correct 0 ms 9304 KB Output is correct
4 Correct 0 ms 9304 KB Output is correct
5 Correct 0 ms 9304 KB Output is correct
6 Correct 0 ms 9304 KB Output is correct
7 Correct 16 ms 9568 KB Output is correct
8 Correct 13 ms 9568 KB Output is correct
9 Correct 13 ms 9568 KB Output is correct
10 Correct 199 ms 12472 KB Output is correct
11 Correct 193 ms 12472 KB Output is correct
12 Correct 166 ms 16904 KB Output is correct
13 Correct 143 ms 12856 KB Output is correct
14 Correct 143 ms 12472 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 14820 KB Output is correct
2 Correct 89 ms 14852 KB Output is correct
3 Correct 69 ms 16900 KB Output is correct
4 Correct 79 ms 16896 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9304 KB Output is correct
2 Correct 0 ms 9304 KB Output is correct
3 Correct 0 ms 9304 KB Output is correct
4 Correct 0 ms 9304 KB Output is correct
5 Correct 0 ms 9304 KB Output is correct
6 Correct 6 ms 9304 KB Output is correct
7 Correct 39 ms 9912 KB Output is correct
8 Correct 389 ms 16904 KB Output is correct
9 Correct 419 ms 16900 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 16908 KB Output is correct
2 Correct 326 ms 16872 KB Output is correct
3 Correct 309 ms 16900 KB Output is correct
4 Correct 459 ms 16904 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9304 KB Output is correct
2 Correct 0 ms 9304 KB Output is correct
3 Correct 0 ms 9304 KB Output is correct
4 Correct 0 ms 9304 KB Output is correct
5 Correct 6 ms 9304 KB Output is correct
6 Correct 33 ms 9568 KB Output is correct
7 Correct 373 ms 12472 KB Output is correct
8 Correct 546 ms 16904 KB Output is correct
9 Correct 379 ms 12856 KB Output is correct
10 Correct 409 ms 12472 KB Output is correct
11 Correct 353 ms 14820 KB Output is correct
12 Correct 413 ms 14824 KB Output is correct
13 Correct 236 ms 16904 KB Output is correct