Submission #683750

#	Time	Username	Problem	Language	Result	Execution time	Memory
683750		yaufung	The Xana coup (BOI21_xanadu)	C++17	100 / 100	96 ms	22408 KiB

xanadu

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector v(n + 1, vector<int>());
    for (int i = 1; i < n; i++) {
        int r1, r2;
        cin >> r1 >> r2;
        v[r1].emplace_back(r2);
        v[r2].emplace_back(r1);
    }
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector dp(n + 5, vector(4, (long long)1e18));
    // dp[0] = no choose self, 0
    // dp[1] = choose self, 0
    // dp[2] = no choose self, 1
    // dp[3] = choose self, 1

    // choose x:
    //     each child choose min(dp[2], dp[3])
    //     each child try swap
    //     update dp[1], dp[3]

    // no choose x:
    //     each child choose min(dp[0], dp[1])
    //     each child try swap
    //     update dp[0], dp[2]

    //problem of only one child?
    auto dfs = [&](auto&& dfs, int x, int last) -> void {
        if (v[x].size() == 1 && last != -1) {
            if (a[x] == 0) {
                dp[x][0] = 0;
                dp[x][1] = 1e9;
                dp[x][2] = 1e9;
                dp[x][3] = 1;
            }
            else {
                dp[x][0] = 1e9;
                dp[x][1] = 1;
                dp[x][2] = 0;
                dp[x][3] = 1e9;
            }
            return;
        }
        for (auto i : v[x]) {
            if (i == last) continue;
            dfs(dfs, i, x);
        }
        int ct = 1 - a[x];
        long long sum = 1;
        for (auto i : v[x]) {
            if (i == last) continue;
            if (dp[i][2] < dp[i][3]) {
                sum += dp[i][2];
            }
            else {
                sum += dp[i][3];
                ct++;
            }
        }
        long long mn = 1e9;
        for (auto i : v[x]) {
            if (i == last) continue;
            if (dp[i][2] < dp[i][3]) mn = min(mn, sum - dp[i][2] + dp[i][3]);
            else mn = min(mn, sum - dp[i][3] + dp[i][2]);
        }
        if (ct % 2 == 0) {
            dp[x][1] = sum;
            dp[x][3] = mn;
        }
        else {
            dp[x][3] = sum;
            dp[x][1] = mn;
        }
        ct = a[x];
        sum = 0;
        for (auto i : v[x]) {
            if (i == last) continue;
            if (dp[i][0] < dp[i][1]) {
                sum += dp[i][0];
            }
            else {
                sum += dp[i][1];
                ct++;
            }
        }
        mn = 1e9;
        for (auto i : v[x]) {
            if (i == last) continue;
            if (dp[i][0] < dp[i][1]) mn = min(mn, sum - dp[i][0] + dp[i][1]);
            else mn = min(mn, sum - dp[i][1] + dp[i][0]);
        }
        if (ct % 2 == 0) {
            dp[x][0] = sum;
            dp[x][2] = mn;
        }
        else {
            dp[x][2] = sum;
            dp[x][0] = mn;
        }
    };
    dfs(dfs, 1, -1);
    // for (int i = 1; i <= n; i++) {
    //     cout << i << ":\n";
    //     for (int j = 0; j <= 3; j++) {
    //         cout << "  " << j << ": " << dp[i][j] << endl;
    //     }
    // }
    long long ans = min(dp[1][0], dp[1][1]);
    if (ans >= 1e9) cout << "impossible\n";
    else cout << ans << "\n";
    return 0;
}

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