oj.uz

Submission #922648

# Submission time Handle Problem Language Result Execution time Memory
922648 2024-02-05T21:32:05 Z OAleksa Synchronization (JOI13_synchronization) C++14
100 / 100
 876 ms 34968 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 3 ms 8792 KB Output is correct
7 Correct 11 ms 9560 KB Output is correct
8 Correct 11 ms 9564 KB Output is correct
9 Correct 11 ms 9652 KB Output is correct
10 Correct 177 ms 29780 KB Output is correct
11 Correct 196 ms 29960 KB Output is correct
12 Correct 571 ms 33916 KB Output is correct
13 Correct 63 ms 29632 KB Output is correct
14 Correct 107 ms 29264 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 31760 KB Output is correct
2 Correct 149 ms 31504 KB Output is correct
3 Correct 191 ms 33284 KB Output is correct
4 Correct 169 ms 33244 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8688 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 4 ms 8796 KB Output is correct
7 Correct 30 ms 10076 KB Output is correct
8 Correct 712 ms 34640 KB Output is correct
9 Correct 789 ms 34640 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 705 ms 34832 KB Output is correct
2 Correct 307 ms 34344 KB Output is correct
3 Correct 296 ms 34620 KB Output is correct
4 Correct 299 ms 34568 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8668 KB Output is correct
4 Correct 3 ms 8540 KB Output is correct
5 Correct 3 ms 8796 KB Output is correct
6 Correct 16 ms 9820 KB Output is correct
7 Correct 219 ms 30832 KB Output is correct
8 Correct 876 ms 34968 KB Output is correct
9 Correct 88 ms 30664 KB Output is correct
10 Correct 160 ms 30436 KB Output is correct
11 Correct 237 ms 32972 KB Output is correct
12 Correct 229 ms 32896 KB Output is correct
13 Correct 297 ms 34492 KB Output is correct