Submission #959823

#	Time	Username	Problem	Language	Result	Execution time	Memory
959823		josanneo22	The Xana coup (BOI21_xanadu)	C++17	100 / 100	47 ms	18816 KiB

xanadu

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

#define L(i,j,k) for(int i=(j);i<=(k);++i)
#define R(i,j,k) for(int i=(j);i>=(k);--i)
#define rep(i, n) L(i, 1, n)
#define all(x) x.begin(),x.end()
#define me(x,a) memset(x,a,sizeof(x))

#include<random>
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int nax = 1E5 + 500;
int N, a[nax], dp[nax][2][2];
vector<int> G[nax];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	
	cin >> N;
	L(i, 1, N - 1) {
		int u, v; cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	L(i, 1, N) cin >> a[i];
	function<void(int, int)> dfs = [&](int u, int f) {
		for (auto & v : G[u]) {
			if (v == f) continue;
			dfs(v, u);
		}
		/* each node is only pressed once and we need to pass on info to the parent node
		 * dp[u][A][B] = minimum amount of operations done when we have considered node u
		 * and we have A = whether we have pressed node u and B = have we pressed an odd or even number of buttons
		 */
		for (int press = 0; press < 2; press++) { // do I want to press this button
			for (int par = 0; par < 2; par++) { // whether we want to pass on to the parent
				int even = 0, odd = N * 2; // initially we only pressed even number of buttons
				for (auto & v : G[u]) {
					if (v == f) continue;
					// dp[v][whether we pressed child][passing to parent of v that is u (our state whether we want to press)]
					int _od = min(odd + dp[v][0][press], even + dp[v][1][press]); // either odd + 1 -> even or even + 1 -> odd
					int _ev = min(odd + dp[v][1][press], even + dp[v][0][press]); // opposite way
					swap(_od, odd); swap(_ev, even);
				}
				if (press ^ par ^ a[u]) dp[u][press][par] = odd + press; // press ^ par ^ a[u] == 1, we need to perform an operation
				else dp[u][press][par] = even + press; // otherwise
				// the value is stored in odd when we want to change because pressing a odd amount of buttons will cause the button to be flipped
			}
		}
	};
	dfs(1, 1);
	int ans = min(dp[1][1][0], dp[1][0][0]); // since the third one shows how the parent would be pressed, there is no parent so no need to consider
	if (ans > N) cout << "impossible\n";
	else cout << ans << '\n';
}

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