Submission #1190071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190071		justinlgl20	The Xana coup (BOI21_xanadu)	C++20	100 / 100	63 ms	22088 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
#define all(x) (x).begin(), (x).end()
 
template<template<typename> class Container, typename G>
ostream& operator<<(ostream& os, Container<G> x) {
    int f = 0; os << '{'; for (auto &i: x) os << (f++ ? ", " : ""), os << i; os << "}";
    return os;
}
 
void _print() {cerr << "]\n";}
 
template<typename T, typename... V>
void _print(T t, V... v) {cerr << t; if (sizeof...(v)) cerr <<", "; _print(v...);}
 
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif

#define pii pair<int, int>
#define f first
#define s second

vector<int> adj[100005];
int dp[100005][2][2];

int32_t main() {
	int n;cin>>n;
	for(int i=0;i<n-1;i++){
		int u,v;cin>>u>>v;adj[u].emplace_back(v);adj[v].emplace_back(u);
	}
	vector<int>a(n+3);for(int i=1;i<=n;i++)cin>>a[i];
	function<void(int,int)>dfs=[&](int u,int p){
		for(int i=0;i<2;i++){
			dp[u][a[u]^i][i]=i; 
			dp[u][a[u]^1ll^i][i]=1e9; // not right amount of stuff to have parent and this dude
		}
		int a=0,b=0; // a is pressing us, b is not pressing us
		// dp[u][0][0] is pressing neither of us which means kid must have a parity of 
		for(int i:adj[u]){
			if(i==p)continue;
			dfs(i,u);
			for(int j=0;j<2;j++){
				// j is whether u is being pressed
				a=dp[u][0][j],b=dp[u][1][j];
				dp[u][0][j] = min(dp[i][j][0]+a, b+dp[i][j][1]); // j is whether or not we are pressing u, if we press a parent we gotta press the kid as well no?
				dp[u][1][j] = min(dp[i][j][1]+a, b+dp[i][j][0]);
			}
		}
	};
	dfs(1,0);
	int ans=min(dp[1][0][0],dp[1][0][1]);
	if(ans>n){
		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