Submission #922648

#	Time	Username	Problem	Language	Result	Execution time	Memory
922648		OAleksa	Synchronization (JOI13_synchronization)	C++14	100 / 100	876 ms	34968 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
const int N = 1e5 + 69;
const int K = 17;
int tin[N], tout[N], timer;
int up[N][K], dep[N], vis[N], f[N], sz[N];
int n, m, q, ans[N], e[N];
vector<int> g[N];
pair<int, int> edges[N];
void add(int v, int val) {
	for (int i = v;i < N;i += (i & -i))
		f[i] += val;
}
int get(int v) {
	int res = 0;
	for (int i = v;i > 0;i -= (i & -i))
		res += f[i];
	return res;
}
bool anc(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a, int b) {
	if (anc(a, b))	
		return a;
	else if (anc(b, a))
		return b;
	for (int i = K - 1;i >= 0;i--) {
		if (!anc(up[a][i], b) && up[a][i] > 0)
			a = up[a][i];
	}
	return up[a][0];
}
void dfs(int v, int p) {
	ans[v] = 1;
	tin[v] = ++timer;
	up[v][0] = p;
	for (int i = 1;i < K;i++)
		up[v][i] = up[up[v][i - 1]][i - 1];
	for (auto u : g[v]) {
		if (u == p)
			continue;
		dep[u] = dep[v] + 1;
		dfs(u, v);
	}
	tout[v] = timer;
}
int Up(int v, int d) {
	int r = v;
	for (int i = 0;i < K;i++) {
		if (d & (1 << i))
			r = up[r][i];
	}
	return r;
}
int find_set(int v) {
	int l = 0, r = dep[v], res = v;
	while (l <= r) {
		int mid = (l + r) / 2;
		int cand = Up(v, mid);
		if (get(tin[v]) - get(tin[cand]) == dep[v] - dep[cand]) {
			res = cand;
			l = mid + 1;
		}
		else
			r = mid - 1;
	}
	return res;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n >> m >> q;
  	for (int i = 1;i <= n - 1;i++) {
  		int a, b;
  		cin >> a >> b;
  		g[a].push_back(b);
  		g[b].push_back(a);
  		edges[i] = {a, b};
  	}
  	dfs(1, 0);
  	while (m--) {
  		int x;
  		cin >> x;
  		int a, b;
  		tie(a, b) = edges[x];
  		if (dep[a] < dep[b])
  			swap(a, b);
  		int par = find_set(b);	
  		if (vis[x]) {
  			add(tin[a], -1);
  			add(tout[a] + 1, 1);
  			e[x] = ans[par];
  			ans[a] = ans[par];
  		}
  		else {
  			ans[par] += ans[a] - e[x];
  			add(tin[a], 1);
  			add(tout[a] + 1, -1);
  		}
  		vis[x] = !vis[x];
  	}
  	while (q--) {
  		int x;
  		cin >> x;
  		cout << ans[find_set(x)] << '\n';
  	}
  }
  return 0;
}

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