Submission #1034069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034069		juicy	Synchronization (JOI13_synchronization)	C++17	100 / 100	201 ms	23148 KiB

synchronization

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
 
const int N = 1e5 + 5, LG = 17;
 
int n, m, q;
int tin[N], tout[N], pr[LG][N], s[N], lst[N], sz[N];
bool vs[N];
array<int, 2> edges[N];
vector<int> g[N];
 
void upd(int i, int x) {
	for (; i <= n; i += i & -i) {
		s[i] += x;
	}
}
 
void upd(int i, int j, int x) {
	upd(i, x);
	upd(j + 1, -x);
}
 
int qry(int i) {
	int res = 0;
	for (; i; i -= i & -i) {
		res += s[i];
	}
	return res;
}
 
int order;
 
void dfs(int u) {
	tin[u] = ++order;
	for (int v : g[u]) {
		if (v != pr[0][u]) {
			pr[0][v] = u;
			for (int j = 1; j < LG; ++j) {
				pr[j][v] = pr[j - 1][pr[j - 1][v]];
			}
			dfs(v);
		}
	}
	tout[u] = order;
}
 
int get(int u) {
	int x = qry(tin[u]);
	for (int j = LG - 1; ~j; --j) {
		if (pr[j][u] && qry(tin[pr[j][u]]) == x) {
			u = pr[j][u];
		}
	}
	return u;
}
 
void add(int u, int x) {
	upd(tin[u], tout[u], x);
}
 
void mrg(int u, int v, int id) {
	u = get(u);
	add(v, -1);
	sz[u] += sz[v] - lst[id];
}
 
void cut(int u, int v, int id) {
	u = get(u);
	lst[id] = sz[v] = sz[u];
	add(v, 1);
}
 
int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
 
	cin >> n >> m >> q;
	for (int i = 1; i < n; ++i) {
		int u, v; cin >> u >> v;
		edges[i] = {u, v};
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1);
	for (int i = 1; i <= n; ++i) {
		sz[i] = 1;
		add(i, 1);
	}
	for (int id = 1; id < N; ++id) {
		if (pr[0][edges[id][0]] == edges[id][1]) {
			swap(edges[id][0], edges[id][1]);
		}
	}
	for (int i = 1; i <= m; ++i) {
		int id; cin >> id;
		vs[id] ^= 1;
		if (vs[id]) {
			mrg(edges[id][0], edges[id][1], id);
		} else {
			cut(edges[id][0], edges[id][1], id);
		}
	}
	while (q--) {
		int u; cin >> u;
		cout << sz[get(u)] << "\n";
	}
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40