Submission #1123144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123144		crafticat	The Xana coup (BOI21_xanadu)	C++17	0 / 100	1098 ms	46160 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) {
    F0R(i, 2) {
        F0R(j, 2) {
            vi child;
            for (auto y : g[x]) {
                if (y == p) continue;
                child.push_back(y);
                solve(y, x);
            }

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


            F0R(f, 1 << child.size()) {
                bitset<20> b = f;
                ll sum = 0, sumJ = 0;
                F0R(y, child.size()) {
                    sum += dp[child[y]][(j + state[child[y]]) % 2][b[y]];
                    sumJ += b[y];
                }
                if (sumJ % 2 == (i + j + state[x] + 1) % 2)
                    best = min(best, sum);
            }

            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][1][0], dp[1][1][1]);
    if (r >= INF) {
        cout << "impossible\n";
    } else
        cout << r;

    return 0;
}

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