Submission #1288381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288381		pasta	The Xana coup (BOI21_xanadu)	C++20	100 / 100	59 ms	17620 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;

#define int                         long long

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
#define S  second
#define F  first
#define all(x)		(x).begin(),(x).end()
#define migmig       ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define deb(x) cerr << (#x) << " " << (x) << endl


//#define lc							id << 1
//#define rc							lc|1
//#define mid							((l + r)/2)

const int maxn = 1e5 + 10;
//const int maxk = 101;
const int mod = 998244353;
const int inf = 1e9 + 1;
const int LOG = 21;

int n, a[maxn], dp[maxn][2][2];
vector<int> G[maxn];

void dfs(int v, int p) {
	if (a[v] == 0) {
		dp[v][1][1] = 1;
		dp[v][1][0] = inf;
		dp[v][0][0] = 0;
		dp[v][0][1] = inf;
	}
	else {
		dp[v][1][1] = inf;
		dp[v][1][0] = 1;
		dp[v][0][0] = inf;
		dp[v][0][1] = 0;
	}
	for (int u : G[v]) {
		if (u != p) {
			dfs(u, v);
			int x = dp[v][0][0], y = dp[v][0][1];
			dp[v][0][0] = min(x + dp[u][0][0], y + dp[u][1][0]);
			dp[v][0][1] = min(x + dp[u][1][0], y + dp[u][0][0]);
			
			x = dp[v][1][0], y = dp[v][1][1];
			dp[v][1][0] = min(x + dp[u][0][1], y + dp[u][1][1]);
			dp[v][1][1] = min(x + dp[u][1][1], y + dp[u][0][1]);
		}
	}
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			dp[v][i][j] = min(inf, dp[v][i][j]);
		}
	}
}

signed main() {
	migmig;
	cin >> n;
	for (int i = 1; i < n; i++) {
		int v, u;
		cin >> v >> u;
		G[v].pb(u);
		G[u].pb(v);
	}
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	
	dfs(1, 0);
	int ans = min(dp[1][0][0], dp[1][1][0]);
	if (ans >= inf) {
		cout << "impossible" << '\n';
	}
	else {
		cout << ans << '\n';
	}
}

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