Submission #676617

#	Time	Username	Problem	Language	Result	Execution time	Memory
676617		YENGOYAN	The Xana coup (BOI21_xanadu)	C++17	100 / 100	90 ms	16888 KiB

xanadu

/*
	//\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\
	\\                                    //
	//  271828___182845__904523__53602__  \\
	\\  87___47____13______52____66__24_  //
	//  97___75____72______47____09___36  \\
	\\  999595_____74______96____69___67  //
	//  62___77____24______07____66__30_  \\
	\\  35___35____47______59____45713__  //
	//                                    \\
	\\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\//
											  */

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_map>
#include <cmath>
#include <climits>
#include <algorithm>
#include <random>
#include <queue>
#include <deque>
#include <iomanip>
#include <string>
#include <tuple>
#include <bitset>
#include <chrono>
#include <ctime>
#include <fstream>
#include <stack>
#include <cstdio>

using namespace std;
using ll = long long;
const int N = 1e5 + 5;
const ll mod = 1e9 + 7, inf = 1e12;

int n;
ll dp[N][2][2];
vector<vector<int>> gp;
vector<int> col;

void dfs(int u, int p) {
	for (int& v : gp[u]) {
		if (v != p) dfs(v, u);
	}
	int cnt_child = gp[u].size() - (u != 0);
	if (!cnt_child) {
		if (col[u]) {
			dp[u][0][0] = 0;
			dp[u][1][1] = 1;
			dp[u][0][1] = dp[u][1][0] = inf;
		}
		else {
			dp[u][0][0] = dp[u][1][1] = inf;
			dp[u][0][1] = 0;
			dp[u][1][0] = 1;
		}
		return;
	}
	// dp[u][i][j]
	// i -> gagat, j -> cnox
	ll res = 0, mn = 2e9, cnt = 0;
	for (int v : gp[u]) {
		if (v == p) continue;	
		res += min(dp[v][0][0], dp[v][1][0]);
		if (dp[v][1][0] <= dp[v][0][0]) {
			++cnt;
		}
		mn = min(mn, abs(dp[v][0][0] - dp[v][1][0]));
	}
	if (col[u] && cnt % 2) dp[u][0][0] = res + mn;
	else if (!col[u] && cnt % 2 == 0) dp[u][0][0] = res + mn;
	else dp[u][0][0] = res;
	if (!col[u] && cnt % 2) dp[u][0][1] = res + mn;
	else if (col[u] && cnt % 2 == 0) dp[u][0][1] = res + mn;
	else dp[u][0][1] = res;
	res = 0, mn = 2e9, cnt = 0;
	for (int& v : gp[u]) {
		if (v == p) continue;
		res += min(dp[v][0][1], dp[v][1][1]);
		if (dp[v][1][1] <= dp[v][0][1]) ++cnt;
		mn = min(mn, abs(dp[v][0][1] - dp[v][1][1]));
	}
	if (col[u] && cnt % 2 == 0) dp[u][1][0] = res + mn + 1;
	else if (!col[u] && cnt % 2) dp[u][1][0] = res + mn + 1;
	else dp[u][1][0] = res + 1;
	if (!col[u] && cnt % 2 == 0) dp[u][1][1] = res + mn + 1;
	else if (col[u] && cnt % 2) dp[u][1][1] = res + mn + 1;
	else dp[u][1][1] = res + 1;
	//if(!u)
}

void solve() {
	cin >> n;
	gp = vector<vector<int>>(n);
	col = vector<int>(n);
	for (int i = 1; i < n; ++i) {
		int u, v; cin >> u >> v;
		gp[--u].push_back(--v);
		gp[v].push_back(u);
	}
	for (int i = 0; i < n; ++i)  cin >> col[i], col[i] = !col[i];
	dfs(0, -1);
	/*for (int i = 0; i < n; ++i) {
		cout << dp[i][0][0] << " " << dp[i][0][1] << " " << dp[i][1][0] << " " << dp[i][1][1] << "\n";
	}*/
	ll res = min(dp[0][0][0], dp[0][1][0]);
	if (res > n) cout << "impossible\n";
	else cout << res << "\n";
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	//int ; cin >> _; while (--)
	solve();
}

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