Submission #1278668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278668		PlayVoltz	The Xana coup (BOI21_xanadu)	C++20	100 / 100	64 ms	34060 KiB

xanadu

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
#include <random>
using namespace std;
 
#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

vector<int> vect;
vector<vector<int> > graph;
vector<vector<vector<int> > > dp;

void dfs(int node, int p){
	if (graph[node].size()==1&&p){
		dp[node][vect[node]][0]=0;
		dp[node][!vect[node]][1]=1;
		return;
	}
	int sum0=0, sum1=0, d0=LLONG_MAX/2, d1=LLONG_MAX/2, c0=0, c1=0;
	for (auto num:graph[node])if (num!=p){
		dfs(num, node);
		sum0+=min(dp[num][0][0], dp[num][0][1]);
		sum1+=min(dp[num][1][0], dp[num][1][1]);
		if (dp[num][0][1]<=dp[num][0][0])++c0;
		if (dp[num][1][1]<=dp[num][1][0])++c1;
		d0=min(d0, max(dp[num][0][0], dp[num][0][1])-min(dp[num][0][0], dp[num][0][1]));
		d1=min(d1, max(dp[num][1][0], dp[num][1][1])-min(dp[num][1][0], dp[num][1][1]));
		sum0=min(sum0, LLONG_MAX/2);
		sum1=min(sum1, LLONG_MAX/2);
	}
	dp[node][vect[node]^(c0&1)][0]=sum0;
	dp[node][vect[node]^(c0&1)^1][0]=sum0+d0;
	dp[node][vect[node]^(c1&1)^1][1]=1+sum1;
	dp[node][vect[node]^(c1&1)][1]=1+sum1+d1;
	for (int i=0; i<2; ++i)for (int j=0; j<2; ++j)dp[node][i][j]=min(dp[node][i][j], LLONG_MAX/2);
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, a, b;
	cin>>n;
	vect.resize(n+1);
	graph.resize(n+1);
	dp.resize(n+1, vector<vector<int> >(2, vector<int>(2, LLONG_MAX/2)));
	for (int i=1; i<n; ++i){
		cin>>a>>b;
		graph[a].pb(b);
		graph[b].pb(a);
	}
	for (int i=1; i<=n; ++i)cin>>vect[i];
	dfs(1, 0);
	if (min(dp[1][0][0], dp[1][0][1])==LLONG_MAX/2)cout<<"impossible";
	else cout<<min(dp[1][0][0], dp[1][0][1]);
}

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