oj.uz

Submission #40067

# Submission time Handle Problem Language Result Execution time Memory
40067 2018-01-26T10:01:34 Z minkank Synchronization (JOI13_synchronization) C++14
100 / 100
 851 ms 18432 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;
#define st first
#define nd second

const int N = 1e5 + 5;

int n, m, q, h[N], st[N], en[N], cur, last[N], res[N], it[N * 8];
bool check[2 * N];
vector<int> G[N];
vector<ii> E;

#define mid ((l + r) / 2)

void update(int node, int l, int r, int p, int val) {
	if(p > r || p < l) return;
	if(l == r) { it[node] += val; return; }
	update(node << 1, l, mid, p, val);
	update(node << 1 | 1, mid + 1, r, p, val);
	int Left = it[node << 1], Right = it[node << 1 | 1];
	if(en[Left] > en[Right]) it[node] = Left;
	else it[node] = Right;
}

int find(int node, int l, int r, int p, int val) {
	if(p < l) return 0;
	if(r <= p && en[it[node]] < en[val]) return 0;
	if(l == r) return it[node];
	int Right = find(node << 1 | 1, mid + 1, r, p, val);
	if(Right) return Right;
	return find(node << 1, l, mid, p, val);
}

#undef mid

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

int main() {
	//ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m >> q;
	for(int i = 1; i < n; ++i) {
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
		E.push_back(ii(u, v));
	}
	dfs(1, 1);
	for(int i = 1; i <= n; ++i) res[i] = 1, update(1, 1, 2 * n, st[i], i);
	for(int i = 1; i <= m; ++i) {
		int id;
		cin >> id; id--;
		int u, v;
		u = E[id].st; v = E[id].nd;
		if(h[u] > h[v]) swap(u, v);
		int p = find(1, 1, 2 * n, st[u], u);
		if(!check[id]) {
			res[p] += res[v] - last[v];
			update(1, 1, 2 * n, st[v], -v);
		}
		else {
			res[v] = res[p];
			update(1, 1, 2 * n, st[v], v);
		}
		last[v] = res[v];
		check[id] ^= 1;
	}
	for(int i = 1; i <= q; ++i) {
		int u;
		cin >> u;
		cout << res[find(1, 1, 2 * n, st[u], u)] << '\n';
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9636 KB Output is correct
2 Correct 0 ms 9636 KB Output is correct
3 Correct 1 ms 9636 KB Output is correct
4 Correct 1 ms 9636 KB Output is correct
5 Correct 2 ms 9636 KB Output is correct
6 Correct 4 ms 9636 KB Output is correct
7 Correct 29 ms 10164 KB Output is correct
8 Correct 26 ms 10164 KB Output is correct
9 Correct 37 ms 10164 KB Output is correct
10 Correct 359 ms 13856 KB Output is correct
11 Correct 398 ms 13852 KB Output is correct
12 Correct 309 ms 18428 KB Output is correct
13 Correct 300 ms 14368 KB Output is correct
14 Correct 290 ms 13856 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 16268 KB Output is correct
2 Correct 224 ms 16208 KB Output is correct
3 Correct 191 ms 18428 KB Output is correct
4 Correct 208 ms 18428 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9636 KB Output is correct
2 Correct 0 ms 9636 KB Output is correct
3 Correct 2 ms 9636 KB Output is correct
4 Correct 3 ms 9636 KB Output is correct
5 Correct 2 ms 9636 KB Output is correct
6 Correct 5 ms 9636 KB Output is correct
7 Correct 34 ms 10412 KB Output is correct
8 Correct 466 ms 18428 KB Output is correct
9 Correct 440 ms 18428 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 18428 KB Output is correct
2 Correct 374 ms 18264 KB Output is correct
3 Correct 286 ms 18428 KB Output is correct
4 Correct 414 ms 18432 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9636 KB Output is correct
2 Correct 2 ms 9636 KB Output is correct
3 Correct 2 ms 9636 KB Output is correct
4 Correct 3 ms 9636 KB Output is correct
5 Correct 7 ms 9636 KB Output is correct
6 Correct 51 ms 10164 KB Output is correct
7 Correct 851 ms 13852 KB Output is correct
8 Correct 523 ms 18428 KB Output is correct
9 Correct 477 ms 14368 KB Output is correct
10 Correct 490 ms 13856 KB Output is correct
11 Correct 408 ms 16268 KB Output is correct
12 Correct 436 ms 16268 KB Output is correct
13 Correct 314 ms 18432 KB Output is correct