Submission #632527

#	Time	Username	Problem	Language	Result	Execution time	Memory
632527		l_reho	The Xana coup (BOI21_xanadu)	C++14	0 / 100	75 ms	31568 KiB

xanadu

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#pragma GCC optimize(3)

using namespace std;

#define ll long long
#define x first
#define y second

#define MOD 1000000007

vector<vector<int>> graph;
vector<int> S;
vector<vector<vector<ll>>> dp;
int N;

ll inf = 1e9+5;

void dfs(int n, int p){
	
	if((int)graph[n].size() == 1 && n != 0){
			
		if(S[n]){
			dp[n][0][0] = inf;
			dp[n][0][1] = 1;
			dp[n][1][0] = 0;
			dp[n][1][1] = inf;
		}
		
		if(!S[n]){
			dp[n][0][0] = 0;
			dp[n][0][1] = inf;
			dp[n][1][0] = inf;
			dp[n][1][1] = 1;
		}
		
		return;
	}
	
	ll dp1[2][2][2];
	
	
	for(int i = 0; i < 2; i++){
		for(int j = 0; j < 2; j++){
			for(int k = 0; k < 2; k++) dp1[i][j][k] = 0;
		}
	}
	
	for(int a : graph[n]){
		if(a == p) continue;
		dfs(a, n);
	}
	
	for(int a : graph[n]){
		if(a == p) continue;
		// numero pari di 1
		if((int)graph[n].size() > 2 || n == 0){
			dp1[0][1][0] = min(dp1[1][0][0], dp1[1][1][0]) + dp[a][0][1];
			dp1[0][0][0] = min(dp1[0][0][0], dp1[0][1][0]) + dp[a][0][0];
		}else dp1[0][1][0] = inf, dp1[0][0][0] = inf;
		
		// numero dispari di 1
		dp1[1][1][0] = min(dp1[0][0][0], dp1[0][1][0]) + dp[a][0][1];
		dp1[1][0][0] = min(dp1[1][0][0], dp1[1][1][0]) + dp[a][0][0];
	
	

		if((int)graph[n].size() > 2 || n == 0){
			
			// numero pari di 1
			dp1[0][1][1] = min(dp1[1][0][1], dp1[1][1][1]) + dp[a][1][1];
			dp1[0][0][1] = min(dp1[0][0][1], dp1[0][1][1]) + dp[a][1][0];

		}else dp1[0][1][1] = inf, dp1[0][0][1] = inf;
		
		// numero dispari di 1
		dp1[1][1][1] = min(dp1[0][0][1], dp1[0][1][1]) + dp[a][1][1];
		dp1[1][0][1] = min(dp1[1][0][1], dp1[1][1][1]) + dp[a][1][0];
		
	}
	
	ll min_o_off = min(dp1[1][0][0], dp1[1][1][0]);
	ll min_e_off = min(dp1[0][0][0], dp1[0][1][0]);
	ll min_o_on = min(dp1[1][0][1], dp1[1][1][1]);
	ll min_e_on = min(dp1[0][0][1], dp1[0][1][1]);
	
	// cout<<"DEBUG-->"<<min_o_off<<" "<<min_e_off<<" "<<min_o_on<<" "<<min_e_on<<endl;
	
	if(S[n]){
		dp[n][0][0] = min_o_off;		// tutti i figli devono essere spenti e devo usare min_o
		dp[n][0][1] = min_e_on+1;
		dp[n][1][0] = min_e_off;
		dp[n][1][1] = min_o_on+1;
	}
	
	if(!S[n]){
		dp[n][0][0] = min_e_off;		// tutti i figli devono essere spenti e devo usare min_o
		dp[n][0][1] = min_o_on+1;
		dp[n][1][0] = min_o_off;
		dp[n][1][1] = min_e_on+1;
	}
	
	
}

void solve(){
	// ifstream in("input.txt");
	// ofstream out("output.txt");

	cin>>N;
	graph.assign(N, vector<int>());
	dp.assign(N, vector<vector<ll>>(2, vector<ll>(2, inf))); 
	S.assign(N, false);
	 
	 
	for(int i = 0; i < N-1; i++){
		int a, b;
		cin>>a>>b;
		a--, b--;
		graph[a].push_back(b);
		graph[b].push_back(a);
		
	}
	for(int i = 0; i < N; i++)
		cin>>S[i];
	 
	dfs(0, -1);
	
	ll ans = min(dp[0][0][0], dp[0][0][1]);
	
	if(ans >= inf) cout<<"impossible"<<endl;
	else cout<<ans<<endl;
	 
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0); 
    
    solve();
	
	return 0;
}

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