Submission #720919

#	Time	Username	Problem	Language	Result	Execution time	Memory
720919		Szil	Spring cleaning (CEOI20_cleaning)	C++14	100 / 100	210 ms	18604 KiB

cleaning

#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
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 17 / 17
• Subtask 7: 30 / 30