Submission #680004

#	Time	Username	Problem	Language	Result	Execution time	Memory
680004		WonderfulWhale	The Xana coup (BOI21_xanadu)	C++17	100 / 100	96 ms	27572 KiB

xanadu

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

#define int int64_t
#define pb push_back
#define st first
#define nd second
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

vector<int> G[100009];
int dp[100009][2][2];
bool tab[100009];

void dfs(int x, int y) {
	if(y != 0 and sz(G[x])==1) {
		dp[x][tab[x]][0] = 0;
		dp[x][!tab[x]][0] = 1e9;
		dp[x][!tab[x]][1] = 1;
		dp[x][tab[x]][1] = 1e9;
		return;
	}
	for(int z:G[x]) if(z != y) dfs(z, x);
	for(int a=0;a<2;a++) {
		for(int b=0;b<2;b++) {
			dp[x][a][b] += b;
			priority_queue<int> q;
			for(int z:G[x]) {
				if(z != y) {
					dp[x][a][b] += dp[z][b][0];
					q.push(dp[z][b][0]-dp[z][b][1]);
				}
			}
			if(tab[x]!=a&&b==0||tab[x]==a&&b==1) {
				dp[x][a][b] -= q.top();
				q.pop();
			}
			while(sz(q)>1) {
				int val1, val2;
				val1 = q.top();
				q.pop();
				val2 = q.top();
				q.pop();
				if(val1+val2>0) {
					dp[x][a][b] -= val1+val2;
				} else {
					break;
				}
			}
		}
	}
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	cin >> n;
	for(int i=0;i<n-1;i++) {
		int a, b;
		cin >> a >> b;
		G[a].pb(b);
		G[b].pb(a);
	}
	for(int i=1;i<=n;i++) {
		cin >> tab[i];
	}
	dfs(1, 0);
	if(min(dp[1][0][0], dp[1][0][1])>n) {
		cout << "impossible\n";
		return 0;
	}
	cout << min(dp[1][0][0], dp[1][0][1]) << "\n";
}

Compilation message (stderr)

xanadu.cpp: In function 'void dfs(int64_t, int64_t)':
xanadu.cpp:35:16: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   35 |    if(tab[x]!=a&&b==0||tab[x]==a&&b==1) {
      |       ~~~~~~~~~^~~~~~

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