oj.uz

Submission #40066

# Submission time Handle Problem Language Result Execution time Memory
40066 2018-01-26T10:01:10 Z minkank Synchronization (JOI13_synchronization) C++14
30 / 100
 340 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 2 ms 9796 KB Output is correct
2 Correct 2 ms 9796 KB Output is correct
3 Correct 2 ms 9796 KB Output is correct
4 Correct 0 ms 9796 KB Output is correct
5 Correct 2 ms 9796 KB Output is correct
6 Correct 3 ms 9796 KB Output is correct
7 Correct 23 ms 10240 KB Output is correct
8 Correct 27 ms 10240 KB Output is correct
9 Correct 22 ms 10240 KB Output is correct
10 Correct 340 ms 13992 KB Output is correct
11 Correct 327 ms 13992 KB Output is correct
12 Correct 216 ms 18432 KB Output is correct
13 Correct 176 ms 14428 KB Output is correct
14 Correct 249 ms 13992 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 16380 KB Output is correct
2 Correct 147 ms 16328 KB Output is correct
3 Correct 96 ms 18432 KB Output is correct
4 Correct 107 ms 18432 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9796 KB Output is correct
2 Correct 2 ms 9796 KB Output is correct
3 Correct 2 ms 9796 KB Output is correct
4 Correct 2 ms 9796 KB Output is correct
5 Correct 0 ms 9796 KB Output is correct
6 Correct 3 ms 9796 KB Output is correct
7 Runtime error 14 ms 10548 KB Execution killed because of forbidden syscall writev (20)
8 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 216 ms 18432 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9796 KB Output is correct
2 Correct 0 ms 9796 KB Output is correct
3 Correct 0 ms 9796 KB Output is correct
4 Correct 3 ms 9796 KB Output is correct
5 Correct 4 ms 9796 KB Output is correct
6 Runtime error 24 ms 10240 KB Execution killed because of forbidden syscall writev (20)
7 Halted 0 ms 0 KB -