Submission #1123159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123159		crafticat	The Xana coup (BOI21_xanadu)	C++17	100 / 100	118 ms	44872 KiB

xanadu

#include <bits/stdc++.h>

using namespace std;
#define F0R(i, n) for (ll i = 0; i < n;i++)
#define FOR(i, j, n) for (ll i = j;i < n;i++)

using ll = long long;
template<typename T>
using V = vector<T>;
using vi = V<ll>;
constexpr ll INF = 1e9 + 7;
using pi = pair<ll,ll>;
using vvi = V<vi>;

vvi g;
V<vvi> dp;
vi state;

void solve(ll x, ll p) {
    vi child;
    for (auto y : g[x]) {
        if (y == p) continue;
        child.push_back(y);
        solve(y, x);
    }

    F0R(i, 2) {
        F0R(j, 2) {

            if (child.empty()) {
                dp[x][1][1] = 1;
                dp[x][0][0] = 0;
                continue;
            }
            ll best = INF;

            vi sDp(2, INF); sDp[0] = 0;

            for (auto y : child) {
                vi newDp(2, INF);
                F0R(k, 2) {
                    F0R(l, 2) {
                        newDp[k] = min(newDp[k], dp[y][(j + state[y]) % 2][l] + sDp[(k + l) % 2]);
                    }
                }
                sDp = newDp;
            }
            best = sDp[(i + j) % 2];

            dp[x][i][j] = best + j;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    ll n; cin >> n; g.resize(n + 1), state.resize(n + 1);
    F0R(i, n - 1) {
        ll a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    F0R(i, n)
        cin >> state[i + 1];

    dp.resize(n + 1, vvi(2, vi(2, INF)));
    solve(1, -1);

    ll r =  min(dp[1][state[1]][0], dp[1][state[1]][1]);
    if (r >= INF) {
        cout << "impossible\n";
    } else
        cout << r;

    return 0;
}

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