Submission #659976

#	Time	Username	Problem	Language	Result	Execution time	Memory
659976		ymm	The Xana coup (BOI21_xanadu)	C++17	100 / 100	64 ms	16908 KiB

xanadu

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100'010;
vector<int> A[N];
int a[N];
int n;

array<int, 4> dfs(int v, int p)
{
	int mnch[2] = {N, N};
	int sum[2] = {0, 1};
	int s[2] = {a[v], !a[v]};
	for (int u : A[v]) {
		if (u == p)
			continue;
		auto arr = dfs(u, v);
		if (arr[0] < arr[2]) {
			sum[0] += arr[0];
			mnch[0] = min(mnch[0], arr[2]-arr[0]);
		} else {
			sum[0] += arr[2];
			mnch[0] = min(mnch[0], arr[0]-arr[2]);
			s[0] ^= 1;
		}
		if (arr[1] < arr[3]) {
			sum[1] += arr[1];
			mnch[1] = min(mnch[1], arr[3]-arr[1]);
		} else {
			sum[1] += arr[3];
			mnch[1] = min(mnch[1], arr[1]-arr[3]);
			s[1] ^= 1;
		}
	}
	array<int, 4> ans;
	ans[0] = s[0]? sum[0] + mnch[0]: sum[0];
	ans[1] = s[0]? sum[0]: sum[0] + mnch[0];
	ans[2] = s[1]? sum[1] + mnch[1]: sum[1];
	ans[3] = s[1]? sum[1]: sum[1] + mnch[1];
	return ans;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop (i,1,n) {
		int v, u;
		cin >> v >> u;
		--v; --u;
		A[v].push_back(u);
		A[u].push_back(v);
	}
	Loop (i,0,n)
		cin >> a[i];
	auto arr = dfs(0, -1);
	int ans = min(arr[0], arr[2]);
	if (ans >= N)
		cout << "impossible\n";
	else
		cout << ans << '\n';
}

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