Submission #484881

#	Time	Username	Problem	Language	Result	Execution time	Memory
484881		wmch13	The Xana coup (BOI21_xanadu)	C++14	100 / 100	117 ms	20464 KiB

xanadu

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 9;
const int INF = (int) 1e5 + 1;

vector <int> adj[N];
int state[N], dp[N][2][2];

int calcDP (int v, int flag1, int flag2, int p) {
	if (dp[v][flag1][flag2] != -1)
		return dp[v][flag1][flag2];
		
	int curState = (state[v] + flag1 + flag2) % 2;
	int minEven = 0, minOdd = INF;
	for (auto u: adj[v]) {
		if (u == p)
			continue;
		
		int r1 = calcDP (u, flag2, 0, v);
		int r2 = calcDP (u, flag2, 1, v);
		
		int copyMinEven = minEven;
		minEven = min (minEven + r1, minOdd + r2);
		minOdd  = min (minOdd + r1, copyMinEven + r2);
	}
	
	int res = flag2;
	res += (curState) ? minOdd : minEven;
	return dp[v][flag1][flag2] = res;
}

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

	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		
		adj[u].push_back (v);
		adj[v].push_back (u);
	}
	
	for (int i = 1; i <= n; i++)
		cin >> state[i];
	
	memset (dp, -1, sizeof (dp));
	int ans = min (calcDP (1, 0, 0, -1), calcDP (1, 0, 1, -1));
	
	if (ans > n) {
		puts ("impossible");
		return 0;
	}
	
	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