Submission #632624

#	Time	Username	Problem	Language	Result	Execution time	Memory
632624		l_reho	The Xana coup (BOI21_xanadu)	C++14	30 / 100	85 ms	31784 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];
	
	
	for(int i = 0; i < 2; i++){
		for(int j = 0; j < 2; j++){
			dp1[i][j] = i == 0 ? 0 : inf;
		}
	}
	
	for(int a : graph[n]){
		if(a == p) continue;
		dfs(a, n);
	}
	
	int i = 0;
	for(int a : graph[n]){
		if(a == p) continue;
		// numero pari di 1
		
		int new_0_0;
		int new_1_0;
		int new_0_1;
		int new_1_1;
		
		
		
		if(!i)
			new_0_0 = min(inf, dp[a][0][0]);
		else
			new_0_0 = min(dp1[1][0] + dp[a][0][1], dp1[0][0] + dp[a][0][0]);
		
		// numero dispari di 1
		new_1_0 = min(dp1[0][0] + dp[a][0][1], dp1[1][0] + dp[a][0][0]);
	
		if(!i)
			new_0_1 = min(inf, dp[a][1][0]);
		else
			new_0_1 = min(dp1[1][1] + dp[a][1][1], dp1[0][1] + dp[a][1][0]);
		
		// numero dispari di 1
		new_1_1 = min(dp1[0][1] + dp[a][1][1], dp1[1][1] + dp[a][1][0]);
	
	
		dp1[0][0] = new_0_0;
		dp1[1][0] = new_1_0;
		dp1[0][1] = new_0_1;
		dp1[1][1] = new_1_1;
		
		
		i++;
	}
	
	
	ll min_o_off = dp1[1][0];
	ll min_e_off = dp1[0][0];
	ll min_o_on = dp1[1][1];
	ll min_e_on = dp1[0][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: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 0 / 40
• Subtask 5: 0 / 30