Submission #1034044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034044		juicy	Synchronization (JOI13_synchronization)	C++17	50 / 100	273 ms	25108 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], dep[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) {
	assert(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]];
			}
			dep[v] = dep[u] + 1;
			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) {
	assert(u == get(u) || v == get(v)); 
	u = get(u), v = get(v);
	add(dep[u] < dep[v] ? v : u, -1);
	sz[u] = sz[u] + sz[v] - lst[id];
}

void cut(int u, int v, int id) {
	if (dep[u] > dep[v]) {
		swap(u, v);
	}
	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 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: 0 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 0 / 40