Submission #574275

#	Time	Username	Problem	Language	Result	Execution time	Memory
574275		amunduzbaev	The Xana coup (BOI21_xanadu)	C++17	100 / 100	86 ms	29796 KiB

xanadu

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

#define ar array
#define int long long
const int N = 1e5 + 5;
vector<int> edges[N];
int a[N], dp[2][2][N];

void dfs(int u, int p = -1){
	vector<ar<int, 2>> t[2];
	dp[0][0][u] = dp[0][1][u] = dp[1][0][u] = dp[1][1][u] = N;
	for(auto x : edges[u]){
		if(x == p) continue;
		dfs(x, u);
		t[0].push_back({dp[0][0][x], dp[0][1][x]});
		t[1].push_back({dp[1][0][x], dp[1][1][x]});
	}
	int m = t[0].size();
	if(!m){
		dp[a[u]][0][u] = 0, dp[a[u] ^ 1][1][u] = 1;
		return;
	}
	
	for(int k=0;k<2;k++){
		int res = 0;
		for(auto x : t[k]) res += x[0];
		sort(t[k].begin(), t[k].end(), [&](auto& a, auto& b){
			return (a[1] - a[0] < b[1] - b[0]);
		});
		for(int x=0;x<=m;x++){
			int is = a[u] ^ (x & 1) ^ k;
			dp[is][k][u] = min(dp[is][k][u], res + k);
			if(x < m){
				res = res - t[k][x][0] + t[k][x][1];
			}
		}
	}
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	for(int i=1;i<n;i++){
		int a, b; cin>>a>>b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	
	dfs(1);
	int res = min(dp[0][0][1], dp[0][1][1]);
	if(res >= N){
		cout<<"impossible\n";
	} else {
		cout<<res<<"\n";
	}
}

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