Submission #547976

#	Time	Username	Problem	Language	Result	Execution time	Memory
547976		fhvirus	Synchronization (JOI13_synchronization)	C++17	100 / 100	459 ms	21356 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;

const int kL = 17;
const int kN = 100'001;
int N, M, Q;
int X[kN], Y[kN];
vector<int> aj[kN];

int in[kN], ou[kN], tot;
int jp[kL][kN];

void dfs(int u, int p) {
	jp[0][u] = p;
	in[u] = ++tot;
	for (const int& v: aj[u]) {
		if (v == p) continue;
		dfs(v, u);
	}
	ou[u] = tot;
}

int val[kN];
void mo(int p, int v) {
	for (; p <= N; p += p & -p)
		val[p] += v;
}
int qu(int p) {
	int r = 0;
	for (; p > 0; p -= p & -p)
		r += val[p];
	return r;
}

int gh(int u) {
	int v = qu(in[u]);
	for (int l = kL - 1; l >= 0; --l)
		if (qu(in[jp[l][u]]) == v)
			u = jp[l][u];
	return u;
}

int ans[kN], tag[kN];
bitset<kN> st;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> M >> Q;

	for (int i = 1; i + 1 <= N; ++i) {
		cin >> X[i] >> Y[i];
		aj[X[i]].push_back(Y[i]);
		aj[Y[i]].push_back(X[i]);
	}

	dfs(1, 1);

	for (int l = 1; l < kL; ++l)
		for (int i = 1; i <= N; ++i)
			jp[l][i] = jp[l - 1][jp[l - 1][i]];

	for (int i = 1; i <= N; ++i) {
		mo(in[i], 1);
		mo(ou[i] + 1, -1);
	}

	fill(ans + 1, ans + N + 1, 1);
	fill(tag + 1, tag + N + 1, 1);

	for (int D, i = 1; i <= M; ++i) {
		cin >> D;
		int u = (X[D] == jp[0][Y[D]] ? Y[D] : X[D]);
		if (st[D]) {
			int h = gh(u);
			ans[u] = ans[h];
			mo(in[u], 1);
			mo(ou[u] + 1, -1);
		} else {
			mo(in[u], -1);
			mo(ou[u] + 1, 1);
			int h = gh(u);
			ans[h] += tag[u];
			tag[h] += tag[u];
			tag[u] = 0;
		}
		st.flip(D);
	}

	for (int C, i = 1; i <= Q; ++i) {
		cin >> C;
		cout << ans[gh(C)] << '\n';
	}

	return 0;
}

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