Submission #1277274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277274		vlomaczk	The Xana coup (BOI21_xanadu)	C++20	100 / 100	65 ms	46988 KiB

xanadu

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int M = 100'010;
vector<vector<int>> g(M), W(M, vector<int>(2, 0)), N(M, vector<int>(2, 0));
vector<int> val(M);

int inf = 1e7;

void dp_dfs(int v, int p) {
	vector<int> taken(2), sum(2), zastap(2, inf);
	int sasiad = 0;
	for(auto u : g[v]) {
		if(u==p) continue;
		sasiad++;
		dp_dfs(u, v);
		for(int k : {0,1}) {
			sum[k] += min(N[u][k], W[u][k]);
			if(W[u][k] <= N[u][k]) taken[k]++;
			zastap[k] = min(zastap[k], max(W[u][k],N[u][k]) - min(W[u][k],N[u][k]));
		}
	}
	if(!sasiad) {
		W[v][val[v]^1] = 1;
		W[v][val[v]] = inf;
		N[v][val[v]^1] = inf;
		N[v][val[v]] = 0;
		//for(int k : {0,1}) cout << v << " " << k << ": " << W[v][k] << " " << N[v][k] << "\n";
		return;
	}
	int K1 = val[v]^(taken[0]%2);
	N[v][K1] = sum[0]; N[v][K1^1] = sum[0]+zastap[0];
	int K2 = val[v]^(taken[1]%2) ^ 1;
	W[v][K2] = 1 + sum[1]; W[v][K2^1] = 1+sum[1]+zastap[1];
	for(int k : {0,1}) {
		W[v][k] = min(W[v][k], inf);
		N[v][k] = min(N[v][k], inf);
		//cout << v << " " << k << ": " << W[v][k] << " " << N[v][k] << "\n";
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;
	for(int i=1; i<n; ++i) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for(int i=1; i<=n; ++i) cin >> val[i];
	int R = 1;
	dp_dfs(R, 0);
	int ans = min(W[R][0], N[R][0]);
	if(ans>=inf) cout << "impossible\n";
	else cout << ans << "\n";

	return 0;
}

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