oj.uz

Submission #720918

# Submission time Handle Problem Language Result Execution time Memory
720918 2023-04-09T19:34:44 Z Szil Spring cleaning (CEOI20_cleaning) C++14
18 / 100
 221 ms 19276 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-tree[pos[1]+n].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

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3156 KB Output is correct
2 Correct 28 ms 3184 KB Output is correct
3 Correct 48 ms 10460 KB Output is correct
4 Correct 54 ms 8464 KB Output is correct
5 Correct 64 ms 10820 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 3796 KB Output is correct
2 Correct 37 ms 4120 KB Output is correct
3 Correct 45 ms 19276 KB Output is correct
4 Correct 102 ms 18632 KB Output is correct
5 Correct 58 ms 17768 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 5004 KB Output is correct
2 Correct 33 ms 4616 KB Output is correct
3 Correct 15 ms 4468 KB Output is correct
4 Incorrect 12 ms 4996 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

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

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 11124 KB Output is correct
2 Correct 117 ms 15652 KB Output is correct
3 Incorrect 135 ms 15000 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

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