Submission #1086649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086649		ZeroCool	The Xana coup (BOI21_xanadu)	C++14	100 / 100	45 ms	20668 KiB

xanadu

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define int long long
#define ld long double
#define crash assert(69 == 420)

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

const int MOD = 1e9 + 7;
const int INF = 1e9;
const int N = 2e5  + 20;
const int LOG = 20;

int dp[N][2][2];
bool A[N];
vector<int> g[N];

void dfs(int x,int p){
	dp[x][A[x]][0] = 0;
	dp[x][A[x] ^ 1][1] = 1;
	for(auto u: g[x]){
		if(u == p)continue;
		dfs(u, x);
		int ndp[2][2];
		for(int i = 0;i < 2;i++){
			for(int j = 0;j < 2;j++)ndp[i][j] = INF;
		}
		for(int i = 0;i < 2;i++){
			for(int j = 0;j < 2;j++){
				for(int k = 0;k < 2;k ++){
					ndp[i ^ j][k] = min(ndp[i ^ j][k], dp[x][i][k] + dp[u][k][j]);
				}
			}
		}
		for(int i = 0;i < 2;i++){
			for(int j = 0;j < 2;j++)dp[x][i][j] = ndp[i][j];
		}
	}
}

signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
	int n;
	cin>>n;
	for(int i = 1;i < n;i++){
		int u, v;
		cin>>u>>v;
		--u, --v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i = 0;i < n;i++)cin>>A[i];
	for(int i = 0;i < n;i++){
		for(int j = 0;j < 2;j++){
			for(int k = 0;k < 2;k++)dp[i][j][k] = INF;
		}
	}
	dfs(0, 0);
	int ans = min(dp[0][0][0], dp[0][0][1]);
	if(ans >= INF)cout<<"impossible";
	else cout<<ans;
}

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