Submission #525907

#	Time	Username	Problem	Language	Result	Execution time	Memory
525907		Qingyu	The Xana coup (BOI21_xanadu)	C++17	100 / 100	108 ms	56928 KiB

xanadu

#include <bits/stdc++.h>

const int N = 1e6 + 50;

std::vector<int> G[N];
int a[N], dp[N][2][2], g[N][2][2], h[2][2];

void dfs(int x, int fa = 0) {
	memset(g[x], 0x3f, sizeof g[x]);
	g[x][0][0] = g[x][1][0] = 0;
	for (int y : G[x])
		if (y != fa) {
			dfs(y, x);
			memcpy(h, g[x], sizeof h);
			for (int o : {0, 1})
				for (int p : {0, 1})
					g[x][o][p] = std::min(0x3f3f3f3f, std::min(h[o][p] + dp[y][0][o], h[o][!p] + dp[y][1][o]));

		}
	for (int o : {0, 1})
		for (int p : {0, 1})
			dp[x][o][a[x] ^ o ^ p] = g[x][o][p] + o;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	int n;
	std::cin >> n;
	for (int i = 1; i < n; ++i) {
		int x, y;
		std::cin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	for (int i = 1; i <= n; ++i) std::cin >> a[i];
	memset(dp, 0x3f, sizeof dp);
	dfs(1);
	int ans = std::min(dp[1][0][0], dp[1][1][0]);
	if (ans > n) {
		puts("impossible");
	}
	else {
		printf("%d\n", ans);
	}
	return 0;
}

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