Submission #912762

#	Time	Username	Problem	Language	Result	Execution time	Memory
912762		NK_	The Xana coup (BOI21_xanadu)	C++17	100 / 100	123 ms	37996 KiB

xanadu

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

using ll = long long;
template<class T> using V = vector<T>;
using vi = V<int>;
using vl = V<ll>;

const int INF = 1e9 + 10;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;

	V<vi> adj(N); for(int i = 0; i < N - 1; i++) {
		int u, v; cin >> u >> v; --u, --v;
		adj[u].pb(v);
		adj[v].pb(u);
	}	

	vi on(N); for(auto& x : on) cin >> x;

	V<V<vl>> dp(N, V<vl>(2, vl(2, INF)));

	function<void(int, int)> dfs = [&](int u, int p) {
		int amt = 0;
		for(auto& v : adj[u]) if (v != p) { dfs(v, u); amt++; }

		if (amt == 0) {
			// cout << u << " => " << on[u] << endl;
			dp[u][on[u]][0] = 0;
			dp[u][on[u] ^ 1][1] = 1;
		} else {
			for(int f = 0; f < 2; f++) {
				ll took = 0, flip = 0; vi chd;
				for(auto& v : adj[u]) if (v != p) {
					took += dp[v][f][1]; flip ^= 1;
					chd.pb(dp[v][f][0] - dp[v][f][1]);
				}

				sort(begin(chd), end(chd));

				dp[u][on[u] ^ f ^ flip][f] = min(dp[u][on[u] ^ f ^ flip][f], took + f);
				for(int i = 0; i < sz(chd); i++) {
					took += chd[i]; flip ^= 1;
					dp[u][on[u] ^ f ^ flip][f] = min(dp[u][on[u] ^ f ^ flip][f], took + f);
				}
			}
		}

		// cout << u << endl;
		// for(int v = 0; v < 2; v++) for(int f = 0; f < 2; f++) {
		// 	cout << v << " " << f << " ====> " << dp[u][v][f] << endl;
		// }

	};

	dfs(0, -1);

	int ans = min(dp[0][0][0], dp[0][0][1]);
	if (ans == INF) cout << "impossible" << nl;
	else cout << ans << nl;

	exit(0-0);
}

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