Submission #398553

#	Time	Username	Problem	Language	Result	Execution time	Memory
398553		nikatamliani	Synchronization (JOI13_synchronization)	C++14	100 / 100	335 ms	27240 KiB

synchronization

#include "bits/stdc++.h"
#define ll long long
using namespace std;
const int N = 2e5+10, LOG = 20;
int in[N], out[N], t[N], L[N][LOG], ans[N], last[N], is_active[N];
vector<int> g[N];
int n, m, q;
void dfs(int x, int p) {
	static int timer = 0;
	in[x] = ++timer;
	L[x][0] = p;
	for(int i = 1; i < LOG; ++i) {
		L[x][i] = L[L[x][i - 1]][i - 1];
	}
	for(int to : g[x]) {
		if(to != p) {
			dfs(to, x);
		}
	}
	out[x] = ++timer;
}
void upd(int x, int coeff) {
	for(; x <= 2*n; x += x & -x) {
		t[x] += coeff;
	}
}
int sum(int x) {
	int ans = 0;
	for(; x > 0; x -= x & -x) {
		ans += t[x];
	}
	return ans;
}
int parent(int x) {
	int me = sum(in[x]);
	for(int i = LOG - 1; i >= 0; --i) {
		if(L[x][i] && sum(in[L[x][i]]) == me) {
			x = L[x][i];
		}
	}
	return x;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> q;
	vector<array<int, 2>> e(n-1);
	for(auto &x : e) {
		cin >> x[0] >> x[1];
		g[x[0]].push_back(x[1]);
		g[x[1]].push_back(x[0]);
	}
	dfs(1, 0);
	for(int i = 0; i < n-1; ++i) {
		if(L[e[i][0]][0] == e[i][1]) {
			swap(e[i][0], e[i][1]);
		}
	}
	for(int i = 1; i <= n; ++i) {
		ans[i] = 1;
		upd(in[i], 1);
		upd(out[i], -1);
	}
	for(int i = 1; i <= m; ++i) {
		int id; cin >> id; --id;
		int par = e[id][0], child = e[id][1];
		if(is_active[id]) {
			last[child] = ans[child] = ans[parent(par)];
			upd(in[child], 1);
			upd(out[child], -1);
		} else { 
			ans[parent(par)] += ans[child] - last[child];
			upd(in[child], -1);
			upd(out[child], 1);
		}
		is_active[id] ^= 1;
	}
	for(int i = 1; i <= q; ++i) {
		int u; cin >> u;
		cout << ans[parent(u)] << '\n';
	}
}

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