Submission #264453

#	Time	Username	Problem	Language	Result	Execution time	Memory
264453		ruler	Synchronization (JOI13_synchronization)	C++14	100 / 100	617 ms	23844 KiB

synchronization

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

#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
 
////////////////////////////////////////////////////////////////////

const int N = 1e5 + 2, LG = 18;

int E[N << 1][2], M[N << 1], FEN[N], P[LG][N], ST[N], FT[N], DW[N], UP[N], t;
vector<int> G[N];

void Add(int p, int x) { for (p++; p < N; p += p & -p) FEN[p] += x; }
void Add(int l, int r, int x) { Add(l, x), Add(r, - x); }
int Get(int p) {
	int res = 0;
	for (; p; p -= p & -p) res += FEN[p];
	return res;
}
int Cnt(int v) { return Get(ST[v] + 1); }
void DFS(int v, int p = 0) {
	ST[v] = t++, P[0][v] = p, DW[v] = 1;
	for (int i = 1; i < LG; i++) P[i][v] = P[i - 1][P[i - 1][v]];
	for (int u : G[v]) if (u != p) DFS(u, v);
	FT[v] = t;
}
int GetRoot(int v) {
	int cnt = Cnt(v);
	for (int i = LG - 1; i >= 0; i--)
		if (P[i][v] != 0 && cnt == Cnt(P[i][v])) v = P[i][v];
	return v;
}

int main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	mt19937 Rnd(time(0));

	int n, m, q; cin >> n >> m >> q;
	for (int i = 1; i < n; i++) {
		int v, u; cin >> v >> u;
		G[v].push_back(u), G[u].push_back(v);
		E[i][0] = v, E[i][1] = u;
	}
	DFS(1);
	for (int i = 2; i <= n; i++) Add(ST[i], FT[i], +1);
	for (int i = 1; i < n; i++) if (P[0][E[i][1]] == E[i][0]) swap(E[i][0], E[i][1]);
	while (m--) {
		int i; cin >> i;
		int v = E[i][0], u = E[i][1];
		if (M[i]) {
			Add(ST[v], FT[v], + 1);
			DW[v] = UP[v] = DW[GetRoot(u)];
		} else {
			Add(ST[v], FT[v], -1);
			DW[GetRoot(u)] += DW[v] - UP[v];
		}
		M[i] ^= 1;
	}
	while (q--) {
		int v; cin >> v;
		cout << DW[GetRoot(v)] << endl;
	}

	return 0;
}

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