Submission #1172620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172620		Troll321	Spring cleaning (CEOI20_cleaning)	C++20	34 / 100	1097 ms	17992 KiB

cleaning

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

ll n, q, cnt, root, query[MAXN];
bool parity[MAXN];
vector<ll> adjl[MAXN];

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

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

void solve() {
	ll ans = cnt-1;
	dfs(root, root, &ans);

	if(parity[root] == 1) {
		cout << "-1\n";
		return ;
	}

	cout << (ans-1) << "\n";
	return ;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> q;
	cnt = n;
	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;}
	}

	while(q--) {
		// Input
		ll d;
		cin >> d;
		for (int i = 0; i < d; ++i) {
			cin >> query[i];
			cnt++;
			adjl[cnt].push_back(query[i]);
			adjl[query[i]].push_back(cnt);
		}

		solve();

		// Reset
		for (int i = 0; i < d; ++i) {
			adjl[n+i+1].clear();
			adjl[query[i]].pop_back();
		}
		cnt = n;
	}
	return 0;
}

• 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