oj.uz

Submission #720919

# Submission time Handle Problem Language Result Execution time Memory
720919 2023-04-09T19:36:38 Z Szil Spring cleaning (CEOI20_cleaning) C++14
100 / 100
 210 ms 18604 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;

struct Node {
	int s = 0;
	int left = 0;
	int cnt = 0;
};

vector<int> g[MAXN];
int depth[MAXN], parent[MAXN], pos[MAXN], head[MAXN], heavy[MAXN], timer = 0, n, q, leaf[MAXN];
Node tree[2 * MAXN];

void build() {
	for (int i = 2 * n; i > n; i--) {
		tree[i].cnt = 1;
	}
	for (int i = n; i >= 1; i--) {
		tree[i].cnt = tree[2*i].cnt + tree[2*i+1].cnt;
	}
}

int dfs(int u, int d) {
	depth[u] = d;
	int s = 1, max_s = 0;
	for (int v : g[u])  {
		if (v != parent[u]) {
			parent[v] = u;
			int k = dfs(v, d + 1);
			s += k;
			if (k > max_s) {
				max_s = k;
				heavy[u] = v;
			}
		}
	}
	return s;
}

void decomp(int u, int h) {
	head[u] = h;
	pos[u] = ++timer;
	if (heavy[u])
		decomp(heavy[u], h);
	for (int v : g[u]) {
		if (v != parent[u] && v != heavy[u])
			decomp(v, v);
	}
}

void apply(int u) {
	tree[u].s = tree[u].cnt - tree[u].s;
	if (u <= n) tree[u].left ^= 1;
}

void build(int u) {
	while (u > 1) {
		u /= 2;
		tree[u].s = tree[2*u].s + tree[2*u+1].s;
		if (tree[u].left == 1)
			tree[u].s = tree[u].cnt - tree[u].s;
	}
}

int qry() {
	return tree[1].cnt-tree[1].s;
}
 
void segupd(int l, int r) {
	l += n; r += n;
	int a = l, b = r;
	while (l <= r) {
		if (l % 2 == 1) apply(l++);
		if (r % 2 == 0) apply(r--);
		l /= 2; r /= 2;
	}
	build(a);
	build(b);
}

void upd(int a, int b) {

	for (; head[a] != head[b]; b = parent[head[b]]) {
		if (depth[head[a]] > depth[head[b]])
			swap(a, b);
		segupd(pos[head[b]], pos[b]);
	}
	if (depth[a] > depth[b])
		swap(a, b);
	segupd(pos[a], pos[b]);
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> q;
	for (int i = 0; i < n - 1; i++) {
		int a, b; cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	dfs(1, 0);
	decomp(1, 1);
	build();

	int leaves = 0;

	for (int i = 1; i <= n; i++) {
		leaf[i] = g[i].size() == 1;
		if (leaf[i]) {
			upd(1, i);
			leaves++;
		}
	}

	while (q--) {
		int c; cin >> c;
		vector<int> v(c);
		for (int i = 0; i < c; i++) {
			cin >> v[i];

			if (leaf[v[i]] == 1) {
				leaf[v[i]] = 2;
			} else {
				upd(1, v[i]);
				leaves++;
			}
		}
		if (leaves % 2 == 1) {
			cout << "-1\n";
		} else {
			cout << n - 2 + c + qry() << "\n";
		}

		for (int i = 0; i < c; i++) {

			if (leaf[v[i]] == 2) {
				leaf[v[i]] = 1;
			} else {
				upd(1, v[i]);
				leaves--;
			}
		}

	}
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 71 ms 4324 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3156 KB Output is correct
2 Correct 32 ms 3156 KB Output is correct
3 Correct 45 ms 10612 KB Output is correct
4 Correct 56 ms 8516 KB Output is correct
5 Correct 65 ms 10776 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3796 KB Output is correct
2 Correct 37 ms 3796 KB Output is correct
3 Correct 41 ms 18140 KB Output is correct
4 Correct 90 ms 17128 KB Output is correct
5 Correct 42 ms 16756 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 4948 KB Output is correct
2 Correct 34 ms 4284 KB Output is correct
3 Correct 20 ms 4224 KB Output is correct
4 Correct 15 ms 4692 KB Output is correct
5 Correct 13 ms 5204 KB Output is correct
6 Correct 37 ms 5308 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 8024 KB Output is correct
2 Correct 210 ms 7864 KB Output is correct
3 Correct 112 ms 6156 KB Output is correct
4 Correct 164 ms 9164 KB Output is correct
5 Correct 192 ms 9192 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 11060 KB Output is correct
2 Correct 137 ms 13736 KB Output is correct
3 Correct 116 ms 13132 KB Output is correct
4 Correct 115 ms 16212 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 71 ms 4324 KB Output is correct
3 Correct 27 ms 3156 KB Output is correct
4 Correct 32 ms 3156 KB Output is correct
5 Correct 45 ms 10612 KB Output is correct
6 Correct 56 ms 8516 KB Output is correct
7 Correct 65 ms 10776 KB Output is correct
8 Correct 38 ms 3796 KB Output is correct
9 Correct 37 ms 3796 KB Output is correct
10 Correct 41 ms 18140 KB Output is correct
11 Correct 90 ms 17128 KB Output is correct
12 Correct 42 ms 16756 KB Output is correct
13 Correct 47 ms 4948 KB Output is correct
14 Correct 34 ms 4284 KB Output is correct
15 Correct 20 ms 4224 KB Output is correct
16 Correct 15 ms 4692 KB Output is correct
17 Correct 13 ms 5204 KB Output is correct
18 Correct 37 ms 5308 KB Output is correct
19 Correct 121 ms 8024 KB Output is correct
20 Correct 210 ms 7864 KB Output is correct
21 Correct 112 ms 6156 KB Output is correct
22 Correct 164 ms 9164 KB Output is correct
23 Correct 192 ms 9192 KB Output is correct
24 Correct 182 ms 11060 KB Output is correct
25 Correct 137 ms 13736 KB Output is correct
26 Correct 116 ms 13132 KB Output is correct
27 Correct 115 ms 16212 KB Output is correct
28 Correct 125 ms 8748 KB Output is correct
29 Correct 125 ms 14880 KB Output is correct
30 Correct 66 ms 12096 KB Output is correct
31 Correct 92 ms 18604 KB Output is correct
32 Correct 179 ms 9116 KB Output is correct
33 Correct 101 ms 12908 KB Output is correct
34 Correct 125 ms 15388 KB Output is correct
35 Correct 120 ms 15420 KB Output is correct