Submission #446020

#	Time	Username	Problem	Language	Result	Execution time	Memory
446020		apostoldaniel854	The Xana coup (BOI21_xanadu)	C++14	100 / 100	78 ms	23156 KiB

xanadu

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define dbg(x) cerr << #x << " " << x << "\n"


const int MAX_N = 1e5;

vector <int> gr[1 + MAX_N];

ll dp[1 + MAX_N][2][2];
int on[1 + MAX_N];

/// dp[node][switched 0/1][value given 0/1] =
void calc_dp (int node, int par) {
    ll offset1 = 1, offset2 = 0;
    ll flip_offset1 = (1 << 30), flip_offset2 = (1 << 30);
    bool state1 = not on[node], state2 = on[node];
    for (int son : gr[node]) {
        if (son != par) {
            calc_dp (son, node);
            /// we switch node
            if (dp[son][0][1] < dp[son][1][1]) {
                offset1 += dp[son][0][1];
                flip_offset1 = min (flip_offset1, dp[son][1][1] - dp[son][0][1]);
            }
            else {
                offset1 += dp[son][1][1];
                flip_offset1 = min (flip_offset1, dp[son][0][1] - dp[son][1][1]);
                state1 ^= 1;
            }
            /// we don't switch node
            if (dp[son][0][0] < dp[son][1][0]) {
                offset2 += dp[son][0][0];
                flip_offset2 = min (flip_offset2, dp[son][1][0] - dp[son][0][0]);
            }
            else {
                offset2 += dp[son][1][0];
                flip_offset2 = min (flip_offset2, dp[son][0][0] - dp[son][1][0]);
                state2 ^= 1;
            }
        }
    }
    dp[node][1][state1] = offset1;
    dp[node][1][not state1] = offset1 + flip_offset1;
    dp[node][0][state2] = offset2;
    dp[node][0][not state2] = offset2 + flip_offset2;
}

int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        gr[x].push_back (y);
        gr[y].push_back (x);
    }
    for (int i = 1; i <= n; i++)
        cin >> on[i];

    calc_dp (1, 0);
    ll ans = min (dp[1][0][0], dp[1][1][0]);
    if (ans > n)
        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