Submission #568118

#	Time	Username	Problem	Language	Result	Execution time	Memory
568118		inluminas	The Xana coup (BOI21_xanadu)	C++17	0 / 100	81 ms	14996 KiB

xanadu

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

#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX
#define l first
#define r second

const int lmt=1e5+10;
vector<int>adj[lmt];
bool on[lmt];
int dp[lmt][2][2];

void check(int u,int p,int ver){
	bool tata=0;
	int val=0,one=0;
	vector<int>a;
	for(int v:adj[u]){
		if(v==p) continue;

		if(dp[v][ver][1]==1e9 && dp[v][ver][0]==1e9){
			tata=1;
			break;
		}else if(dp[v][ver][0]==1e9){
			val+=dp[v][ver][1],one++;
		}else if(dp[v][ver][1]==1e9){
			val+=dp[v][ver][0];
		}else{
			val+=dp[v][ver][0];
			a.push_back(-dp[v][ver][0]+dp[v][ver][1]);
		}
	}
	if(tata) return;
	sort(a.begin(),a.end());
	dp[u][on[u]^((one+ver)%2)][ver]=min(dp[u][on[u]^((one+ver)%2)][ver],val+ver);
	for(int x:a){
		val+=x,one++;
		dp[u][on[u]^((one+ver)%2)][ver]=min(dp[u][on[u]^((one+ver)%2)][ver],val+ver);
	}
	return;
}

void dfs(int u,int p){
	int deg=0;
	for(int v:adj[u]){
		if(v==p) continue;
		dfs(v,u);
		deg++;
	}
	if(!deg){
		dp[u][on[u]][0]=0,dp[u][on[u]^1][1]=1;
		//cout<<dp[u][0][0]<<" "<<dp[u][0][1]<<" "<<dp[u][1][0]<<" "<<dp[u][1][1]<<endl;
		return;
	}else{
		check(u,p,0);
		check(u,p,1);
	}
}

int main(){
	fastio;

	int n;
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	for(int i=1;i<=n;i++){
		bool x;
		cin>>x;
		on[i]=x;
	}

	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]=1e9;
			}
		}
	}

	dfs(1,-1);

	int ans=min(dp[1][0][0],dp[1][0][1]);
	if(ans==1e9) cout<<"Impossible"<<endl;
	else cout<<ans<<endl;
	return 0;
}

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