Submission #1190007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190007		tamyte	The Xana coup (BOI21_xanadu)	C++20	100 / 100	82 ms	32072 KiB

xanadu

#include <bits/stdc++.h>

using namespace std;


int main() {
    int n;
    cin >> n;
    vector<vector<int>> adj(n);
    vector<int> state(n);
    for (int i = 1; i < n; ++i) {
    	int a, b;
    	cin >> a >> b;
    	--a; --b;
    	adj[a].push_back(b);
    	adj[b].push_back(a);
    }
    for (auto& x : state) cin >> x;
    vector<vector<vector<int>>> dp(n,vector<vector<int>>(2, vector<int>(2, -1)));
    auto dfs = [&](auto& dfs, int i, int p, int on, int toggle) -> int {
    	if (dp[i][on][toggle] != -1) return dp[i][on][toggle];
    	array<int, 2> now = {n + 1, n + 1};
    	now[state[i]] = 0;
    	for (auto& j : adj[i]) {
    		if (j == p) continue;
    		array<int, 2> ndp;
    		// dont turn on
    		ndp[0] = dfs(dfs, j, i, toggle, 0);
    		// turn on
    		ndp[1] = dfs(dfs, j, i, toggle, 1);
    		auto nnow = now;
    		nnow[0] = min({n + 1, now[0] + ndp[0], now[1] + ndp[1]});
    		nnow[1] = min({n + 1, now[0] + ndp[1], now[1] + ndp[0]});
    		now = nnow;
    	}
    	return dp[i][on][toggle] = now[(on ^ toggle)] + toggle;
    };
    int res = min(dfs(dfs, 0, -1, 0, 0), dfs(dfs, 0, -1, 0, 1));
    if (res > n) {
    	cout << "impossible\n";
    	return 0;
    }
    cout << res << endl;
}

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