Submission #751027

#	Time	Username	Problem	Language	Result	Execution time	Memory
751027		jmyszka2007	Synchronization (JOI13_synchronization)	C++17	100 / 100	737 ms	30436 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
constexpr int LIM = 2e5;
constexpr int base = (1 << 18);
pair<int, int>kr[LIM + 10];
vector<int>g[LIM + 10];
int kt[LIM + 10];
int val[LIM + 10];
int pop[LIM + 10];
int nxt[LIM + 10][19];
int siz[LIM + 10];
int pre[LIM + 10];
int dep[LIM + 10];
int tri[2 * base];
int aktpre = 1;
void dfs(int v, int o) {
	dep[v] = dep[o] + 1;
	pre[v] = aktpre++;
	nxt[v][0] = o;
	for(int i = 1; i <= 18; i++) {
		nxt[v][i] = nxt[nxt[v][i - 1]][i - 1];
	}
	siz[v] = 1;
	for(auto x : g[v]) {
		if(x != o) {
			dfs(x, v);
			siz[v] += siz[x];
		}
	}
}
void upd(int l, int r, int x) {
	l += base;
	r += base;
	while(l <= r) {
		if(l & 1) {
			tri[l] += x;
		}
		if(!(r & 1)) {
			tri[r] += x;
		}
		l = (l + 1) / 2;
		r = (r - 1) / 2;
	}
}
int que(int v) {
	v += base;
	int ans = 0;
	while(v > 0) {
		ans += tri[v];
		v /= 2;
	}
	return ans;
}
int find(int v) {
	for(int i = 18; i >= 0; i--) {
		if(que(pre[v]) - que(pre[nxt[v][i]]) == dep[v] - dep[nxt[v][i]]) {
			v = nxt[v][i];
		}
	}
	return v;
}
void uni(int a, int b) {
	if(pre[a] > pre[b]) {
		swap(a, b);
	}
	upd(pre[b], pre[b] + siz[b] - 1, 1); 
}
void disuni(int a, int b) {
	if(pre[a] > pre[b]) {
		swap(a, b);
	}
	upd(pre[b], pre[b] + siz[b] - 1, -1); 
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	for(int i = 1; i <= n; i++) {
		val[i] = 1;
	}
	for(int i = 1; i < n; i++) {
		cin >> kr[i].st >> kr[i].nd;
		g[kr[i].st].push_back(kr[i].nd);
		g[kr[i].nd].push_back(kr[i].st);
	}
	dfs(1, 1);
	for(int i = 1; i <= m; i++) {
		int x;
		cin >> x;
		kt[x]++;
		if(kt[x] & 1) {
			int tmp = val[find(kr[x].st)] + val[find(kr[x].nd)] - pop[x];
			uni(kr[x].st, kr[x].nd);
			val[find(kr[x].st)] = tmp;
		}
		else {
			pop[x] = val[find(kr[x].st)];
			disuni(kr[x].st, kr[x].nd);
			val[find(kr[x].st)] = pop[x];
			val[find(kr[x].nd)] = pop[x];
		}
	}
	while(q--) {
		int x;
		cin >> x;
		cout << val[find(x)] << '\n';
	}
}

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