Submission #869123

#	Time	Username	Problem	Language	Result	Execution time	Memory
869123		alex_2008	Synchronization (JOI13_synchronization)	C++14	100 / 100	424 ms	27332 KiB

synchronization

#include <iostream>
#include <cmath>
#include <algorithm>
#include <fstream>
#include <set>
#include <tuple>
#include <vector>
#include <iomanip>
#include <queue>
#define yy second
#define xx first
typedef long double ld;
using namespace std;
const int N = 2e5 + 10;
vector <vector<int>> G;
int n;
int inf[N], last[N], tin[N], tout[N], dp[N][20], fenwick[N];
bool ch[N];
int timer = 0;
void dfs(int v, int p) {
	dp[v][0] = p;
	for (int i = 1; i < 20; i++) {
		dp[v][i] = dp[dp[v][i - 1]][i - 1];
	}
	tin[v] = ++timer;
	for (auto it : G[v]) {
		if (it == p) continue;
		dfs(it, v);
	}
	tout[v] = ++timer;
}
void update(int pos, int val) {
	for (int i = pos; i <= 2 * n; i += (i & (-i))) {
		fenwick[i] += val;
	}
}
int sum(int pos) {
	int sm = 0;
	while (pos > 0) {
		sm += fenwick[pos];
		pos -= (pos & (-pos));
	}
	return sm;
}
int par(int v) {
	for (int i = 19; i >= 0; i--) {
		if (sum(tin[dp[v][i]]) == sum(tin[v])) {
			v = dp[v][i];
		}
	}
	return v;
}
int main()
{
	int m, q;
	cin >> n >> m >> q;
	G.resize(n + 1);
	vector <pair<int, int>> Edges = { { 0, 0 } };
	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
		Edges.push_back({ a, b });
	}
	for (int i = 1; i <= n; i++) {
		inf[i] = 1;
		last[i] = 0;
	}
	dfs(1, 1);
	for (int i = 1; i <= n; i++) {
		update(tin[i], -1);
		update(tout[i], 1);
	}
	for (int i = 1; i <= m; i++) {
		int x;
		cin >> x;
		int v = Edges[x].first, u = Edges[x].second;
		if (dp[u][0] == v) swap(v, u);
		if (ch[v]) {
			inf[v] = last[v] = inf[par(u)];
			update(tin[v], -1);
			update(tout[v], 1);
		}
		else {
			inf[par(u)] += (inf[v] - last[v]);
			update(tin[v], 1);
			update(tout[v], -1);
		}
		ch[v] = 1 - ch[v];
	}
	for (int i = 1; i <= q; i++) {
		int x;
		cin >> x;
		cout << inf[par(x)] << "\n";
	}
}

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