Submission #867928

#	Time	Username	Problem	Language	Result	Execution time	Memory
867928		serifefedartar	The Xana coup (BOI21_xanadu)	C++17	100 / 100	56 ms	15892 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+7;
const ll P = 31;
const ll LOGN = 20; 
const ll MAXN = 1e5 + 100;
#define int long long

vector<vector<int>> graph;
int active[MAXN], dp[MAXN][2][2], temp_dp[2];
void act(int node, int parent) {
	temp_dp[0] = 0;
	temp_dp[1] = 1e8;
	for (auto u : graph[node]) {
		if (u == parent)
			continue;
		int td0 = temp_dp[0], td1 = temp_dp[1];
		temp_dp[0] = min(td1 + dp[u][1][1], td0 + dp[u][0][1]);
		temp_dp[1] = min(td1 + dp[u][0][1], td0 + dp[u][1][1]);
	}
	dp[node][1][0] = temp_dp[0] + 1;
	dp[node][1][1] = temp_dp[1] + 1;

	temp_dp[0] = 0;
	temp_dp[1] = 1e8;
	for (auto u : graph[node]) {
		if (u == parent)
			continue;
		int td0 = temp_dp[0], td1 = temp_dp[1];
		temp_dp[0] = min(td1 + dp[u][1][0], td0 + dp[u][0][0]);
		temp_dp[1] = min(td1 + dp[u][0][0], td0 + dp[u][1][0]);
	}
	dp[node][0][1] = temp_dp[0];
	dp[node][0][0] = temp_dp[1];
}

void deact(int node, int parent) {
	temp_dp[0] = 0;
	temp_dp[1] = 1e8;
	for (auto u : graph[node]) {
		if (u == parent)
			continue;
		int td0 = temp_dp[0], td1 = temp_dp[1]; 
		temp_dp[0] = min(td1 + dp[u][1][1], td0 + dp[u][0][1]);
		temp_dp[1] = min(td1 + dp[u][0][1], td0 + dp[u][1][1]);
	}
	dp[node][1][1] = temp_dp[0] + 1;
	dp[node][1][0] = temp_dp[1] + 1;

	temp_dp[0] = 0; 
	temp_dp[1] = 1e8;
	for (auto u : graph[node]) {
		if (u == parent)
			continue;
		int td0 = temp_dp[0], td1 = temp_dp[1];
		temp_dp[0] = min(td1 + dp[u][1][0], td0 + dp[u][0][0]);
		temp_dp[1] = min(td1 + dp[u][0][0], td0 + dp[u][1][0]);
	}
	dp[node][0][0] = temp_dp[0];
	dp[node][0][1] = temp_dp[1];
}

void dfs(int node, int parent) {
	if (graph[node].size() == 1 && node != 1) {
		if (active[node]) {
			dp[node][1][0] = 1;
			dp[node][0][1] = 0;
			dp[node][1][1] = 1e8;
			dp[node][0][0] = 1e8;
		} else {
			dp[node][1][1] = 1;
			dp[node][0][0] = 0;
			dp[node][1][0] = 1e8;
			dp[node][0][1] = 1e8;
		}
		return ;
	}

	for (auto u : graph[node]) {
		if (u == parent)
			continue;
		dfs(u, node);
	}

	if (active[node])
		act(node, parent);
	else
		deact(node, parent);
}

signed main() {
	fast
	int N, a, b;
	cin >> N;

	graph = vector<vector<int>>(N+1, vector<int>());
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < 2; j++)
			for (int q = 0; q < 2; q++)
				dp[i][j][q] = 1e8;
	}
	for (int i = 1; i < N; i++) {
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	for (int i = 1; i <= N; i++)
		cin >> active[i];
	dfs(1, 1);

	if (min(dp[1][0][0], dp[1][1][0]) >= 1e8)
		cout << "impossible\n";
	else
		cout << min(dp[1][0][0], dp[1][1][0]) << "\n";
}

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