Submission #725627

#	Time	Username	Problem	Language	Result	Execution time	Memory
725627		gagik_2007	The Xana coup (BOI21_xanadu)	C++17	100 / 100	152 ms	20644 KiB

xanadu

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;

typedef long long ll;
typedef long double ld;

#define ff first
#define ss second

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 200007;
ll n, m;
vector<int>g[N];
bool vl[N];
ll dp[N][2][2];

void dfs(int v, int par = -1) {
	dp[v][0][0] = dp[v][1][0] = dp[v][1][1] = dp[v][0][1] = MOD;
	bool gnac = false;
	for (int to : g[v]) {
		if (to != par) {
			dfs(to, v);
			gnac = true;
		}
	}
	//cout << v << ": ";
	if (!gnac) {
		dp[v][vl[v]][0] = 0;
		dp[v][!vl[v]][1] = 1;
	}
	else {
		ll mx = 0;
		int cnt = 0;
		for (int to : g[v]) {
			if (to != par) {
				if (dp[to][0][0] <= dp[to][0][1]) {
					mx += dp[to][0][0];
				}
				else {
					mx += dp[to][0][1];
					cnt++;
				}
			}
		}
		cnt %= 2;
		//cout << "cnt = " << cnt << endl;
		//cout << "mx = " << mx << endl;
		bool val = vl[v];
		if (cnt) {
			val = !val;
		}
		dp[v][val][0] = mx;
		ll smx = MOD;
		for (int to : g[v]) {
			if (to != par) {
				smx = min(smx, mx - min(dp[to][0][0], dp[to][0][1])
					+ max(dp[to][0][0], dp[to][0][1]));
			}
		}
		//cout << "smx = " << smx << endl;
		dp[v][!val][0] = smx;

		mx = 0;
		cnt = 0;
		val = vl[v];
		smx = MOD;
		for (int to : g[v]) {
			if (to != par) {
				if (dp[to][1][0] <= dp[to][1][1]) {
					mx += dp[to][1][0];
				}
				else {
					mx += dp[to][1][1];
					cnt++;
				}
			}
		}
		cnt %= 2;
		if (cnt) {
			val = !val;
		}
		dp[v][!val][1] = mx + 1;
		for (int to : g[v]) {
			if (to != par) {
				smx = min(smx, mx - min(dp[to][1][0], dp[to][1][1])
					+ max(dp[to][1][0], dp[to][1][1]));
			}
		}
		dp[v][val][1] = smx + 1;
	}
	//cout << dp[v][0][0] << " " << dp[v][0][1] << " " 
	//	<< dp[v][1][0] << " " << dp[v][1][1] << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for (int i = 1; i <= n; i++) {
		cin >> vl[i];
	}
	dfs(1);
	ll ans = min(dp[1][0][0], dp[1][0][1]);
	cout << (ans >= MOD ? "impossible" : to_string(ans)) << endl;
}

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