Submission #676378

#	Time	Username	Problem	Language	Result	Execution time	Memory
676378		Vahe	The Xana coup (BOI21_xanadu)	C++17	5 / 100	1083 ms	7012 KiB

xanadu

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

int main() {
	int n; cin >> n;
	vector<vector<int>> gp(n);
	for (int i = 1; i < n; i++)
	{
		int u, v; cin >> u >> v;
		gp[--v].push_back(--u);
		gp[u].push_back(v);
	}
	int t = 0;
	for (int i = 0; i < n; i++) { int a; cin >> a; t += a << i; }
	int ans = 2e9;
	for (int i = 0; i < (1 << n); i++)
	{
		int k = t, cnt = 0;
		for (int j = 0; j < n; j++)
		{
			if (i & (1 << j))
			{
				cnt++;
				k ^= (1 << j);
				for (int& u : gp[j]) k ^= (1 << u);
			}
			if (k == 0) ans = min(ans, cnt);
		}
	}
	if (ans == 2e9) cout << "impossible\n";
	else cout << ans << endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 40
• Subtask 5: 0 / 30