Submission #734249

#	Time	Username	Problem	Language	Result	Execution time	Memory
734249		Stickfish	The Xana coup (BOI21_xanadu)	C++17	100 / 100	137 ms	30700 KiB

xanadu

#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std;
using ll = long long;

const int MAXN = 1e5 + 123;
vector<int> edg[MAXN];
ll dp[MAXN][4];
bitset<MAXN> bs;

ll get_mxsm(vector<ll>& v, size_t stid) {
    ll ans = 0;
    for (size_t i = stid; i + 1 < v.size() && v[i] + v[i + 1] < 0; i += 2)
        ans += v[i] + v[i + 1];
    return ans;
}

void dfs(int v, int rt) {
    int p = bs[v];
    if (rt != -1 && edg[v].size() == 1) {
        dp[v][p] = 0;
        dp[v][(p ^ 1) + 2] = 1;
        dp[v][p ^ 1] = MAXN;
        dp[v][p + 2] = MAXN;
        return;
    }
    ll sum0 = 0;
    ll sum1 = 0;
    vector<ll> v0;
    vector<ll> v1;
    for (auto u : edg[v]) {
        if (u == rt)
            continue;
        dfs(u, v);
        sum0 += dp[u][0];
        sum1 += dp[u][1];
        v0.push_back(dp[u][2] - dp[u][0]);
        v1.push_back(dp[u][3] - dp[u][1]);
    }
    sort(v0.begin(), v0.end());
    sort(v1.begin(), v1.end());
    // bs[v] = 0
    dp[v][0] = sum0 + get_mxsm(v0, 0);
    dp[v][1] = sum0 + v0[0] + get_mxsm(v0, 1);
    dp[v][2] = 1 + sum1 + v1[0] + get_mxsm(v1, 1);
    dp[v][3] = 1 + sum1 + get_mxsm(v1, 0);
    if (bs[v]) {
        swap(dp[v][0], dp[v][1]);
        swap(dp[v][2], dp[v][3]);
    }
}

signed main() {
    int n;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        edg[u].push_back(v);
        edg[v].push_back(u);
    }
    for (int i = 0; i < n; ++i) {
        char c;
        cin >> c;
        bs[i] = c == '1';
    }
    dfs(0, -1);
    ll ans = min(dp[0][0], dp[0][2]);
    if (ans > n)
        cout << "impossible\n";
    else
        cout << ans << '\n';
    //for (int i = 0; i < n; ++i) {
        //cout << dp[i][0] << ' ' << dp[i][1] << ' ' << dp[i][2] << ' ' << dp[i][3] << endl;
    //}
}

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