Submission #1172669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172669		Troll321	Spring cleaning (CEOI20_cleaning)	C++20	28 / 100	1097 ms	13496 KiB

cleaning

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 2e5 + 5;

ll n, q, d, initAns, ans = 0, root, parr[MAXN], query[MAXN], plusarr[MAXN];
bool parity[MAXN], isLeaf[MAXN], processed[MAXN];
vector<ll> adjl[MAXN];

void dfs(ll now, ll par) {
	parity[now] = 0;
	parr[now] = par;
	isLeaf[now] = (adjl[now].size() == 1);
	if(isLeaf[now]) {parity[now] = 1;}
	else {
		for(ll nxt : adjl[now]) {
			if(nxt == par) {continue ;}
			dfs(nxt, now);
			parity[now] ^= parity[nxt];
		}
	}

	if(parity[now] == 0) {ans++;}
}


void build() {
	dfs(root, root);
}

bool getRoot() {
	return parity[root];
}

void addLeaf(ll node) {
	ll now = node;
	while(true) {
		parity[now] ^= 1;
		if(parr[now] == now) {break ;}

		now = parr[now];
	}
}

ll ask(ll node) {
	ll out = 0, now = node;
	while(true) {
		out += (parity[now] == 0);
		if(parr[now] == now) {break ;}

		now = parr[now];
	}
	return out;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> q;
	ans = n-1;
	for (int i = 0; i < n-1; ++i) {
		ll a, b;
		cin >> a >> b;
		adjl[a].push_back(b);
		adjl[b].push_back(a);

		if(adjl[a].size() > 1) {root = a;}
		else if(adjl[b].size() > 1) {root = b;}
	}

	root = 1;
	build();

	initAns = ans;
	while(q--) {
		// Input
		ans = initAns;
		cin >> d;
		ans += d;
		for (int i = 0; i < d; ++i) {
			cin >> query[i];
			plusarr[query[i]]++;
		}

		for (int i = 0; i < d; ++i) {
			ll now = query[i];
			if(processed[now]) {continue ;}
			processed[now] = true;

			if((plusarr[now]-isLeaf[now]) % 2) {
				ans -= ask(now);
				addLeaf(now);
				ans += ask(now);
			}
		}

		if(getRoot() == 1) {
			cout << "-1\n";
		} else {
			cout << (ans-1) << "\n";
		}

		// Reset
		for (int i = 0; i < d; ++i) {processed[query[i]] = false;}
		for (int i = 0; i < d; ++i) {
			ll now = query[i];
			if(processed[now]) {continue ;}
			processed[now] = true;

			if((plusarr[now]-isLeaf[now]) % 2) {
				addLeaf(now);
			}
		}
		for (int i = 0; i < d; ++i) {processed[query[i]] = false; plusarr[query[i]] = 0;}
	}
	return 0;
}

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