Submission #904854

#	Time	Username	Problem	Language	Result	Execution time	Memory
904854		vjudge1	The Xana coup (BOI21_xanadu)	C++17	100 / 100	88 ms	26232 KiB

xanadu

#include <iostream>
#include <vector>

#define endl '\n'
#define pb push_back
#define ll long long

using namespace std;

const int MAXN = 1e5+100;
const ll INF = 1e6+109;

int n;
bool a[MAXN], used[MAXN];
vector<int> adj[MAXN];

ll dp[MAXN][2][2];

ll min(ll a, ll b){
	return (a < b)? a : b;
}

void dfs(int v){
	used[v] = 1;


	ll cdp[2][2];
	ll tmp[2][2];

	bool flg = true;

	for(int u : adj[v]){
		if(used[u]) continue;

		dfs(u);

		if(flg){
			for(int i=0; i<2; i++){
				for(int j=0; j<2; j++){
					cdp[i][j] = dp[u][i][j];
					tmp[i][j] = INF;
				}
			}

		}
		else{
			for(int i=0; i<2; i++){
				tmp[i][0] = min(tmp[i][0], cdp[i][0] + dp[u][i][0]);
				tmp[i][0] = min(tmp[i][0], cdp[i][1] + dp[u][i][1]);
				tmp[i][1] = min(tmp[i][1], cdp[i][0] + dp[u][i][1]);
				tmp[i][1] = min(tmp[i][1], cdp[i][1] + dp[u][i][0]);
					
			/*
			if(v == 1){
				cout << "A: "<< endl;
				for(int i=0; i<2; i++){
					for(int j=0; j<2; j++) cout << tmp[i][j] << ' ';
					cout << endl;
				}
			}
			*/

			}


		}

		for(int i=0; i<2; i++){
			for(int j=0; j<2; j++){
				if(!flg) cdp[i][j] = tmp[i][j];
				tmp[i][j] = INF;
			}
		}

		flg = false;
	}

	for(int i=0; i<2; i++){
		for(int j=0; j<2; j++){
			if(a[v]) dp[v][i][j] = cdp[j][i^j^1] + j;
			else dp[v][i][j] = cdp[j][i^j] + j;
			
		}
	}

	if(flg){
		if(a[v]){
			dp[v][1][0] = 0;
			dp[v][0][1] = 1;
			dp[v][1][1] = INF;
			dp[v][0][0] = INF;
		}
		else{
			dp[v][0][0] = 0;
			dp[v][1][1] = 1;
			dp[v][1][0] = INF;
			dp[v][0][1] = INF;
		}
	}
			
}	


int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n;

	for(int i=1; i<n; i++){
		int x, y;

		cin >> x >> y;
		x--;y--;

		adj[x].pb(y);
		adj[y].pb(x);
	}

	for(int i=0; i<n; i++) cin >> a[i];

	dfs(0);

	if(min(dp[0][0][0], dp[0][0][1]) >= INF) cout << "impossible" << endl;
	else cout << min(dp[0][0][0], dp[0][0][1]) << endl;


	return 0;
}

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