Submission #866946

#	Time	Username	Problem	Language	Result	Execution time	Memory
866946		Mizo_Compiler	The Xana coup (BOI21_xanadu)	C++17	100 / 100	55 ms	21600 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
#define pb push_back
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
const int N = 1e5+5;
int n, a[N];
vector<int> adj[N];
ll dp[N][2][2];

ll sol(int u, int pv, int nv, int par) {
	ll &ret = dp[u][pv][nv];
	if (~ret)return ret;
	int cur = (a[u] ^ pv ^ nv);
	if (!cur) {
		ll mn = n+1;
		bool c = 0;
		ret = nv;
		for (auto &v : adj[u]) {
			if (v == par)continue;
			ll f = sol(v, nv, 0, u), s = sol(v, nv, 1, u);
			mn = min(mn, abs(f-s));
			ret += min(f, s);
			if (s < f)c ^= 1;
		}
		if (c)ret += mn;
		return ret;
	} else {
		if (sz(adj[u]) == 1 && u)return ret = n+1;
		ll mn = n+1;
		bool c = 0;
		ret = nv;
		for (auto &v : adj[u]) {
			if (v == par)continue;
			ll f = sol(v, nv, 0, u), s = sol(v, nv, 1, u);
			mn = min(mn, abs(f-s));
			ret += min(f, s);
			if (s < f)c ^= 1;
		}
		if (!c)ret += mn;
		return ret;
	}
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 0; i+1 < n; i++) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		for (int j = 0; j < 2; j++) {
			for (int k = 0; k < 2; k++) {
				dp[i][j][k] = -1;
			}
		}
	}
	ll x = min(sol(0, 0, 1, 0), sol(0, 0, 0, 0));
	if (x > n) {
		cout << "impossible\n";
		return 0;
	}
	cout << x << "\n";
}

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