oj.uz

Submission #1034069

# Submission time Handle Problem Language Result Execution time Memory
1034069 2024-07-25T09:27:27 Z juicy Synchronization (JOI13_synchronization) C++17
100 / 100
 201 ms 23148 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
 
const int N = 1e5 + 5, LG = 17;
 
int n, m, q;
int tin[N], tout[N], pr[LG][N], s[N], lst[N], sz[N];
bool vs[N];
array<int, 2> edges[N];
vector<int> g[N];
 
void upd(int i, int x) {
	for (; i <= n; i += i & -i) {
		s[i] += x;
	}
}
 
void upd(int i, int j, int x) {
	upd(i, x);
	upd(j + 1, -x);
}
 
int qry(int i) {
	int res = 0;
	for (; i; i -= i & -i) {
		res += s[i];
	}
	return res;
}
 
int order;
 
void dfs(int u) {
	tin[u] = ++order;
	for (int v : g[u]) {
		if (v != pr[0][u]) {
			pr[0][v] = u;
			for (int j = 1; j < LG; ++j) {
				pr[j][v] = pr[j - 1][pr[j - 1][v]];
			}
			dfs(v);
		}
	}
	tout[u] = order;
}
 
int get(int u) {
	int x = qry(tin[u]);
	for (int j = LG - 1; ~j; --j) {
		if (pr[j][u] && qry(tin[pr[j][u]]) == x) {
			u = pr[j][u];
		}
	}
	return u;
}
 
void add(int u, int x) {
	upd(tin[u], tout[u], x);
}
 
void mrg(int u, int v, int id) {
	u = get(u);
	add(v, -1);
	sz[u] += sz[v] - lst[id];
}
 
void cut(int u, int v, int id) {
	u = get(u);
	lst[id] = sz[v] = sz[u];
	add(v, 1);
}
 
int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
 
	cin >> n >> m >> q;
	for (int i = 1; i < n; ++i) {
		int u, v; cin >> u >> v;
		edges[i] = {u, v};
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1);
	for (int i = 1; i <= n; ++i) {
		sz[i] = 1;
		add(i, 1);
	}
	for (int id = 1; id < N; ++id) {
		if (pr[0][edges[id][0]] == edges[id][1]) {
			swap(edges[id][0], edges[id][1]);
		}
	}
	for (int i = 1; i <= m; ++i) {
		int id; cin >> id;
		vs[id] ^= 1;
		if (vs[id]) {
			mrg(edges[id][0], edges[id][1], id);
		} else {
			cut(edges[id][0], edges[id][1], id);
		}
	}
	while (q--) {
		int u; cin >> u;
		cout << sz[get(u)] << "\n";
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3672 KB Output is correct
2 Correct 2 ms 3676 KB Output is correct
3 Correct 2 ms 3488 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 2 ms 3460 KB Output is correct
6 Correct 2 ms 3676 KB Output is correct
7 Correct 9 ms 4956 KB Output is correct
8 Correct 9 ms 5012 KB Output is correct
9 Correct 9 ms 5008 KB Output is correct
10 Correct 109 ms 17932 KB Output is correct
11 Correct 98 ms 17744 KB Output is correct
12 Correct 155 ms 22356 KB Output is correct
13 Correct 47 ms 17612 KB Output is correct
14 Correct 74 ms 16628 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 19308 KB Output is correct
2 Correct 57 ms 19328 KB Output is correct
3 Correct 65 ms 21252 KB Output is correct
4 Correct 64 ms 21332 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3672 KB Output is correct
2 Correct 2 ms 3672 KB Output is correct
3 Correct 2 ms 3676 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 2 ms 3676 KB Output is correct
6 Correct 2 ms 3676 KB Output is correct
7 Correct 15 ms 5580 KB Output is correct
8 Correct 201 ms 23016 KB Output is correct
9 Correct 190 ms 23148 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 22864 KB Output is correct
2 Correct 101 ms 22356 KB Output is correct
3 Correct 102 ms 22664 KB Output is correct
4 Correct 100 ms 22452 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3676 KB Output is correct
2 Correct 2 ms 3676 KB Output is correct
3 Correct 2 ms 3676 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 3 ms 3784 KB Output is correct
6 Correct 11 ms 4956 KB Output is correct
7 Correct 131 ms 18572 KB Output is correct
8 Correct 193 ms 22988 KB Output is correct
9 Correct 66 ms 18768 KB Output is correct
10 Correct 111 ms 18000 KB Output is correct
11 Correct 95 ms 20864 KB Output is correct
12 Correct 72 ms 20820 KB Output is correct
13 Correct 103 ms 22612 KB Output is correct