Submission #1214145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214145		pinbu	The Xana coup (BOI21_xanadu)	C++20	10 / 100	52 ms	16964 KiB

xanadu

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

const int N = 100005, oo = 1e9;
void mini(int &X, int Y) {
	if (X >= Y) X = Y;
}

int n;
bool b[N];
vector<int> adj[N];
int dp[N][2][2];
int tmp[2][2][2];
void DFS(int u, int par) {
	tmp[0][0][0] = tmp[0][0][1] = 0;
	tmp[0][1][0] = tmp[0][1][1] = oo;
	int i = 0;
	for (int v: adj[u]) if (v != par) {
		DFS(v, u);
		i++;
		int id = i & 1;
		for (int k = 0; k < 2; k++) {
			tmp[id][k][0] = tmp[id][k][1] = oo;
			mini(tmp[id][k][0], min(tmp[id ^ 1][k ^ 1][0] + dp[v][1][0], tmp[id ^ 1][k][0] + dp[v][0][0]));
			mini(tmp[id][k][1], min(tmp[id ^ 1][k ^ 1][1] + dp[v][1][1], tmp[id ^ 1][k][1] + dp[v][0][1]));
		}
	}
	if (!i) {
		dp[u][0][b[u]] = 0;
		dp[u][1][b[u]] = oo;
		dp[u][0][1 ^ b[u]] = oo;
		dp[u][1][1 ^ b[u]] = 1;
	} else {
		dp[u][0][b[u]] = tmp[i & 1][0][0];
		dp[u][1][b[u]] = 1 + tmp[i & 1][1][1];
		dp[u][0][1 ^ b[u]] = tmp[i & 1][1][0];
		dp[u][1][1 ^ b[u]] = 1 + tmp[i & 1][0][1];
	}
}

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    cin >> n;
    for (int i = 1, u, v; i < n; i++) {
    	cin >> u >> v;
    	adj[u].emplace_back(v);
    	adj[v].emplace_back(u);
    }
    for (int i = 1; i <= n; i++) cin >> b[i];
    DFS(1, 1);
    int ans = min(dp[1][0][0], dp[1][1][0]);
    if (ans >= oo) cout << "impossible";
    else cout << ans;
    
    return 0;
}

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