Submission #1323863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1323863		gohchingjayk	The Xana coup (BOI21_xanadu)	C++20	30 / 100	37 ms	16928 KiB

xanadu

#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

using namespace std;

using ll = long long;

#define int ll

using ii = pair<int, int>;
using iii = pair<ii, int>;

constexpr int INF = 1e18 + 5;
constexpr int MAXN = 100000 + 5;
constexpr int MOD = 1e9 + 7;

int dp[MAXN][2][2];
vector<int> adjlist[MAXN];
bool state[MAXN];

void dfs(int x, int pa) {
	
	dp[x][0][!state[x]] = 0;
	dp[x][0][state[x]] = INF;
	dp[x][1][!state[x]] = INF;
	dp[x][1][state[x]] = 1;
	
	for (int ch : adjlist[x]) {
		if (ch == pa) continue;
		
		dfs(ch, x);
		
		int temp[2][2];
		
		temp[0][0] = min(
			dp[x][0][0] + dp[ch][0][1],
			dp[x][0][1] + dp[ch][1][1]
		);
		
		temp[0][1] = min(
			dp[x][0][0] + dp[ch][1][1],
			dp[x][0][1] + dp[ch][0][1]
		);
		
		temp[1][0] = min(
			dp[x][1][0] + dp[ch][0][0],
			dp[x][1][1] + dp[ch][1][0]
		);
		
		temp[1][1] = min(
			dp[x][1][0] + dp[ch][1][0],
			dp[x][1][1] + dp[ch][0][0]
		);
		
		dp[x][0][0] = temp[0][0];
		dp[x][1][0] = temp[1][0];
		dp[x][0][1] = temp[0][1];
		dp[x][1][1] = temp[1][1];
	}
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

	int N; cin >> N;
	for (int i = 1; i < N; ++i) {
		int u, v; cin >> u >> v;
		adjlist[u].emplace_back(v);
		adjlist[v].emplace_back(u);
	}
	
	for (int i = 1; i <= N; ++i) cin >> state[i];
	
	dfs(1, -1);
	int ans = min(dp[1][0][1], dp[1][1][1]);
	cout << (ans >= INF ? "impossible" : to_string(ans));
}

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