oj.uz

Submission #1034044

# Submission time Handle Problem Language Result Execution time Memory
1034044 2024-07-25T09:00:39 Z juicy Synchronization (JOI13_synchronization) C++17
50 / 100
 273 ms 25108 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], dep[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) {
	assert(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]];
			}
			dep[v] = dep[u] + 1;
			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) {
	assert(u == get(u) || v == get(v)); 
	u = get(u), v = get(v);
	add(dep[u] < dep[v] ? v : u, -1);
	sz[u] = sz[u] + sz[v] - lst[id];
}

void cut(int u, int v, int id) {
	if (dep[u] > dep[v]) {
		swap(u, v);
	}
	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 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Incorrect 2 ms 2908 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 20824 KB Output is correct
2 Correct 107 ms 20728 KB Output is correct
3 Correct 112 ms 23228 KB Output is correct
4 Correct 105 ms 23376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 2 ms 2904 KB Output is correct
3 Correct 1 ms 2904 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 15 ms 5084 KB Output is correct
8 Correct 244 ms 25024 KB Output is correct
9 Correct 273 ms 25108 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 24980 KB Output is correct
2 Correct 157 ms 24404 KB Output is correct
3 Correct 150 ms 24400 KB Output is correct
4 Correct 142 ms 24404 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2820 KB Output is correct
4 Incorrect 1 ms 2904 KB Output isn't correct
5 Halted 0 ms 0 KB -