Submission #528688

#	Time	Username	Problem	Language	Result	Execution time	Memory
528688		d2k05	The Xana coup (BOI21_xanadu)	C++14	100 / 100	101 ms	39636 KiB

xanadu

#include <bits/stdc++.h>

#define fastio ios_base :: sync_with_stdio(0), cin.tie(0);

using namespace std;
using ll = long long;

const int mxN = 1e6 + 5, mod = 1e9 + 7;

int n, a[mxN], dp[mxN][2][2];
vector <int> adj[mxN];

void dfs(int v, int p = -1) {
	int d[2][2], nd[2][2];
	for (int i = 0; i < 2; ++i) {
		for (int j = 0; j < 2; ++j)
			d[i][j] = nd[i][j] = n + 1;
	}
	bool ch = 0;
	for (auto to : adj[v]) {
		if (to != p) {
			dfs(to, v);
			if (!ch) {
				d[0][0] = dp[to][0][0];
				d[0][1] = dp[to][0][1];
				d[1][0] = dp[to][1][0];
				d[1][1] = dp[to][1][1];
				ch = 1;
			}
			else {
				nd[0][0] = min(d[0][0] + dp[to][0][0], d[0][1] + dp[to][0][1]);
				nd[0][1] = min(d[0][0] + dp[to][0][1], d[0][1] + dp[to][0][0]);
				nd[1][0] = min(d[1][0] + dp[to][1][0], d[1][1] + dp[to][1][1]);
				nd[1][1] = min(d[1][0] + dp[to][1][1], d[1][1] + dp[to][1][0]);
				for (int i = 0; i < 2; ++i) {
					for (int j = 0; j < 2; ++j)
						d[i][j] = nd[i][j], nd[i][j] = n + 1;
				}
			}
		}
	}
	if (!ch) {
		if (!a[v]) {
			dp[v][0][0] = 0;
			dp[v][0][1] = n + 1;
			dp[v][1][1] = 1;
			dp[v][1][0] = n + 1;
		}
		else {
			dp[v][0][0] = n + 1;
			dp[v][0][1] = 1;
			dp[v][1][0] = 0;
			dp[v][1][1] = n + 1;
		}
	}
	else {
		if (!a[v]) {
			dp[v][0][0] = d[1][0];
			dp[v][0][1] = d[0][1] + 1;
			dp[v][1][0] = d[1][1];
			dp[v][1][1] = d[0][0] + 1;
		} else {
			dp[v][0][0] = d[1][1];
			dp[v][0][1] = d[0][0] + 1;
			dp[v][1][0] = d[1][0];
			dp[v][1][1] = d[0][1] + 1;
		}
	}
}

int main() {
	fastio;
	cin >> n;
	for (int i = 1, u, v; i < n; ++i) {
		cin >> u >> v;
		adj[u].push_back(v); adj[v].push_back(u);
	}
	for (int i = 1; i <= n; ++i) cin >> a[i], a[i] ^= 1;
	dfs(1);
	if (min(dp[1][1][0], dp[1][1][1]) > n)
		cout << "impossible";
	else cout << min(dp[1][1][0], dp[1][1][1]);
	return 0;
}

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