oj.uz

Submission #59894

# Submission time Handle Problem Language Result Execution time Memory
59894 2018-07-23T09:06:42 Z gusfring Synchronization (JOI13_synchronization) C++14
100 / 100
 595 ms 46676 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 5 ms 2680 KB Output is correct
2 Correct 5 ms 2916 KB Output is correct
3 Correct 5 ms 2916 KB Output is correct
4 Correct 6 ms 2916 KB Output is correct
5 Correct 5 ms 2916 KB Output is correct
6 Correct 7 ms 2948 KB Output is correct
7 Correct 23 ms 3744 KB Output is correct
8 Correct 23 ms 3744 KB Output is correct
9 Correct 28 ms 3780 KB Output is correct
10 Correct 415 ms 10464 KB Output is correct
11 Correct 349 ms 10464 KB Output is correct
12 Correct 303 ms 15056 KB Output is correct
13 Correct 242 ms 15056 KB Output is correct
14 Correct 227 ms 15056 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 15056 KB Output is correct
2 Correct 142 ms 15056 KB Output is correct
3 Correct 147 ms 15056 KB Output is correct
4 Correct 140 ms 15056 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15056 KB Output is correct
2 Correct 6 ms 15056 KB Output is correct
3 Correct 6 ms 15056 KB Output is correct
4 Correct 5 ms 15056 KB Output is correct
5 Correct 5 ms 15056 KB Output is correct
6 Correct 8 ms 15056 KB Output is correct
7 Correct 48 ms 15056 KB Output is correct
8 Correct 475 ms 18448 KB Output is correct
9 Correct 523 ms 21464 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 554 ms 21464 KB Output is correct
2 Correct 330 ms 23740 KB Output is correct
3 Correct 302 ms 25992 KB Output is correct
4 Correct 292 ms 28328 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 28328 KB Output is correct
2 Correct 6 ms 28328 KB Output is correct
3 Correct 7 ms 28328 KB Output is correct
4 Correct 7 ms 28328 KB Output is correct
5 Correct 10 ms 28328 KB Output is correct
6 Correct 51 ms 28328 KB Output is correct
7 Correct 595 ms 28328 KB Output is correct
8 Correct 458 ms 34336 KB Output is correct
9 Correct 437 ms 34336 KB Output is correct
10 Correct 417 ms 34616 KB Output is correct
11 Correct 424 ms 39588 KB Output is correct
12 Correct 317 ms 42400 KB Output is correct
13 Correct 357 ms 46676 KB Output is correct