Submission #33189

#	Time	Username	Problem	Language	Result	Execution time	Memory
33189		aome	Synchronization (JOI13_synchronization)	C++14	100 / 100	546 ms	16908 KiB

synchronization

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40