Submission #263854

#	Time	Username	Problem	Language	Result	Execution time	Memory
263854		atoiz	Synchronization (JOI13_synchronization)	C++14	100 / 100	161 ms	16888 KiB

synchronization

// https://oj.uz/submission/151967

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100007;

int par[MAXN], ch[MAXN][2];
bool isroot(int u) { return (u != ch[par[u]][0] && u != ch[par[u]][1]); }
bool dir(int u) { return (u == ch[par[u]][1]); }
void rotate(int u) 
{
	int p = par[u], g = par[p], d = dir(u);
	if (!isroot(p)) { ch[g][dir(p)] = u; } par[u] = g;
	par[ch[p][d] = ch[u][!d]] = p, par[ch[u][!d] = p] = u;
}
void splay(int u) { for (; !isroot(u); rotate(u)) if (!isroot(par[u])) rotate(dir(u) == dir(par[u]) ? par[u] : u); }
void access(int u) { for (int v = 0; u; v = u, u = par[v]) splay(u), ch[u][1] = v; }
int get(int u)
{
	access(u), splay(u);
	while (ch[u][0]) u = ch[u][0];
	splay(u);
	return u;
}

int N, M, Q, last[MAXN], ans[MAXN], U[MAXN], V[MAXN], prv[MAXN];
bool state[MAXN];
vector<int> G[MAXN];

void dfs(int u, int p) { for (int v : G[u]) if (v != p) dfs(v, prv[v] = u); }

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> M >> Q;
	for (int i = 1; i < N; ++i) {
		cin >> U[i] >> V[i];
		G[U[i]].push_back(V[i]);
		G[V[i]].push_back(U[i]);
	}
	dfs(1, 0);
	for (int u = 1; u <= N; ++u) ans[u] = 1;
	while (M--) {
		int e;
		cin >> e;
		int u = U[e], v = V[e];
		if (prv[v] != u) swap(u, v);
		int r = get(u);
		if (state[e]) {
			last[v] = ans[v] = ans[r];
			access(v), splay(v), par[u] = ch[v][0] = 0;
		} else {
			ans[r] += (ans[v] - last[v]);
			access(v), splay(v), par[v] = u;
		}
		state[e] = !state[e];
	}
	while (Q--) {
		int u;
		cin >> u;
		cout << ans[get(u)] << '\n';
	}
}

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