Submission #936150

#	Time	Username	Problem	Language	Result	Execution time	Memory
936150		shoryu386	The Xana coup (BOI21_xanadu)	C++17	100 / 100	112 ms	25232 KiB

xanadu

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

#define int long long
#define MAX 100007
int n;
vector<int> adj[MAX];

int dp[MAX][2][2];
int active[MAX];

bool comp(pair<int, int> a, pair<int, int> b){
	return a.second - a.first < b.second - b.first;
}

void dfs(int x, int p){
	for (auto y : adj[x]){ if (y == p) continue;
		dfs(y, x);
	}
	
	//we want to find the min presses to make even, and min presses to make odd
	if (true){
		vector<pair<int, int>> competition;
		int cursum = 0;
		for (auto y : adj[x]){ if (y == p) continue;
			competition.push_back({dp[y][0][0], dp[y][1][0]});
			cursum += dp[y][0][0];
		}
		
		int evenbest = cursum, oddbest = INT_MAX;
		sort(competition.begin(), competition.end(), comp);
		
		bool cureven = true;
		for (auto y : competition){
			cureven = !cureven;
			cursum += y.second - y.first;
			
			if (cureven) evenbest = min(evenbest, cursum);
			else oddbest = min(oddbest, cursum);
		}
		
		if (active[x]){
			dp[x][0][0] = oddbest;
			dp[x][0][1] = evenbest;
		}
		else{
			dp[x][0][0] = evenbest;
			dp[x][0][1] = oddbest;
		}
	}
	if (true){
		vector<pair<int, int>> competition;
		int cursum = 0;
		for (auto y : adj[x]){ if (y == p) continue;
			competition.push_back({dp[y][0][1], dp[y][1][1]});
			cursum += dp[y][0][1];
		}
		
		int evenbest = cursum, oddbest = INT_MAX;
		sort(competition.begin(), competition.end(), comp);
		
		bool cureven = true;
		for (auto y : competition){
			cureven = !cureven;
			cursum += y.second - y.first;
			
			if (cureven) evenbest = min(evenbest, cursum);
			else oddbest = min(oddbest, cursum);
		}
		
		if (active[x]){
			dp[x][1][0] = evenbest + 1;
			dp[x][1][1] = oddbest + 1;
		}
		else{
			dp[x][1][0] = oddbest + 1;
			dp[x][1][1] = evenbest + 1;
		}
	}
	
	//cout << x << ' ' << dp[x][0] << ' ' << dp[x][1] << '\n';
}

main(){
	cin >> n;
	for (int x = 0; x < n-1; x++){
		int a, b; cin >> a >> b; a--; b--; adj[a].push_back(b); adj[b].push_back(a);
	}
	for (int x = 0; x < n; x++) cin >> active[x];
	
	dfs(0, -1);
	
	int res = min(dp[0][0][0], dp[0][1][0]);
	
	if (res >= INT_MAX) cout << "impossible";
	else cout << res;
	
}

Compilation message (stderr)

xanadu.cpp:84:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   84 | main(){
      | ^~~~

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