Submission #404004

#	Time	Username	Problem	Language	Result	Execution time	Memory
404004		Nordway	The Xana coup (BOI21_xanadu)	C++17	100 / 100	151 ms	15096 KiB

xanadu

#include <iostream>
#include <vector>
#define pb push_back

using namespace std;

const int N = 1e5 + 1;
const int inf = 1e9;

bool turned[N];

vector <int> g[N];

int dp[N][2][2], tmp[2][2];

void dfs(int v, int p) {
	for (int to : g[v]) {
		if (to != p) {
			dfs(to, v);
		}
	}
	dp[v][turned[v]][0] = 0;
	dp[v][turned[v]][1] = inf;
	dp[v][1 ^ turned[v]][1] = 1;
	dp[v][1 ^ turned[v]][0] = inf;
	for (int to : g[v]) {
		if (to != p) {
			tmp[0][0] = min(tmp[0][0], dp[v][0][0] + dp[to][0][0]);
			tmp[0][0] = min(tmp[0][0], dp[v][1][0] + dp[to][0][1]);
			tmp[0][1] = min(tmp[0][1], dp[v][0][1] + dp[to][1][0]);
			tmp[0][1] = min(tmp[0][1], dp[v][1][1] + dp[to][1][1]);
			tmp[1][0] = min(tmp[1][0], dp[v][0][0] + dp[to][0][1]);
			tmp[1][0] = min(tmp[1][0], dp[v][1][0] + dp[to][0][0]);
			tmp[1][1] = min(tmp[1][1], dp[v][0][1] + dp[to][1][1]);
			tmp[1][1] = min(tmp[1][1], dp[v][1][1] + dp[to][1][0]);
			for (int i = 0; i < 2; i++) {
				for (int j = 0; j < 2; j++) {
					dp[v][i][j] = tmp[i][j];
					tmp[i][j] = inf;
				}
			}
		}
	}
}

int main(){
	int n;
	cin >> n;

	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}

	for (int i = 1; i <= n; i++) {
		cin >> turned[i];
	}

	for (int i : {0, 1}) {
		for (int j : {0, 1}) {
			tmp[i][j] = inf;
		}
	}

	dfs(1, 1);

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

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