Submission #415604

#	Time	Username	Problem	Language	Result	Execution time	Memory
415604		KoD	The Xana coup (BOI21_xanadu)	C++17	100 / 100	117 ms	23236 KiB

xanadu

#include <bits/stdc++.h>

template <class T> using Vec = std::vector<T>;

constexpr int INF = 1000000000;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    Vec<Vec<int>> graph(N);
    for (int i = 0; i < N - 1; ++i) {
        int a, b;
        std::cin >> a >> b;
        a -= 1;
        b -= 1;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    Vec<int> C(N);
    for (auto& x : C) {
        std::cin >> x;
    }
    Vec<std::array<std::array<int, 2>, 2>> dp(N);
    auto dfs = [&](auto&& dfs, const int u, const int p) -> void {
        for (const auto v : graph[u]) {
            if (v != p) {
                dfs(dfs, v, u);
            }
        }
        for (const auto i : { 0, 1 }) {
            auto& cur = dp[u][i];
            cur[C[u] ^ i] = i;
            cur[C[u] ^ i ^ 1] = INF;
            for (const auto v : graph[u]) {
                if (v != p) {
                    std::array<int, 2> next;
                    next.fill(INF);
                    for (const auto j : { 0, 1 }) {
                        for (const auto k : { 0, 1 }) {
                            next[j ^ k] = std::min(next[j ^ k], cur[j] + dp[v][k][i]);
                        }
                    }
                    cur = std::move(next);
                }
            }
        }
    };
    dfs(dfs, 0, -1);
    int ans = INF;
    for (const auto i : { 0, 1 }) {
        ans = std::min(ans, dp[0][i][0]);
    }
    if (ans == INF) {
        std::cout << "impossible\n";
    }
    else {
        std::cout << ans << '\n';
    }
}

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