Submission #720896

#	Time	Username	Problem	Language	Result	Execution time	Memory
720896		Szil	Spring cleaning (CEOI20_cleaning)	C++14	34 / 100	1079 ms	17780 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;

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

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);
	}
}

int qry(int u) {
	u = n + pos[u];
	int res = tree[u];
	for (u /= 2; u >= 1; u /= 2) {
		res ^= tree[u];
	}
	return res;
}

void segupd(int l, int r) {
	l += n; r += n;
	while (l <= r) {
		if (l % 2 == 1) tree[l++] ^= 1;
		if (r % 2 == 0) tree[r--] ^= 1;
		l /= 2; r /= 2;
	}
}

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);

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

	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]);
			}
		}
		if (qry(1) == 1) {
			cout << "-1\n";
		} else {
			int ans = n - 1 + c;
			for (int i = 2; i <= n; i++) {
				if (qry(i) == 0) ans++;
			}
			cout << ans << "\n";
		}

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

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

	}
}

• Subtask 1: 0 / 0
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 17
• Subtask 7: 0 / 30