Submission #742426

#	Time	Username	Problem	Language	Result	Execution time	Memory
742426		penguin133	The Xana coup (BOI21_xanadu)	C++17	100 / 100	106 ms	26696 KiB

xanadu

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

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int memo[100005][2][2], n;
int A[100005];
vector <int> adj[100005];

bool cmp(pi a, pi b){
	return a.fi - a.se < b.fi - b.se;
}

int dp(int x, int par, int f, int f2){
	if(memo[x][f][f2] != -1)return memo[x][f][f2];
	int ok = A[x];
	if(f)ok = !ok;
	if(f2)ok = !ok;
	int ans = 2e9;
	vector <pi> cand;
	int stuf = 0;
	for(auto i : adj[x]){
		if(i == par)continue;
		int x1 = dp(i, x, 1, f);
		int x2 = dp(i, x, 0, f);
		cand.push_back({x1, x2});
		stuf += x2;
	}
	sort(cand.begin(), cand.end(), cmp);
	for(int i=ok-1;i<(int)cand.size();i+=2){
		if(i > 0)stuf += cand[i-1].fi - cand[i-1].se;
		if(i >= 0)stuf += cand[i].fi - cand[i].se;
		ans = min(ans, stuf);
	}
	if(f)ans++;
	return memo[x][f][f2] = ans;
}

void solve(){
	cin >> n;
	for(int i=1;i<n;i++){
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for(int i=1;i<=n;i++)cin >> A[i];
	memset(memo, -1, sizeof(memo));
	int tmp = min(dp(1, -1, 0, 0), dp(1, -1, 1, 0));
	if(tmp > n)cout << "impossible";
	else cout << tmp;
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

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

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