Submission #676410

#	Time	Username	Problem	Language	Result	Execution time	Memory
676410		c2zi6	The Xana coup (BOI21_xanadu)	C++14	10 / 100	152 ms	25384 KiB

xanadu

#include <bits/stdc++.h>
#define PUT(a, b) freopen(a, "r", stdin); freopen(b, "w", stdout)

using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;

ll n;
vector<vector<ll>> gp;
vector<ll> st;

vector<ll> bb, wb, bw, ww;
ll bbf(ll, ll);
ll wbf(ll, ll);
ll bwf(ll, ll);
ll wwf(ll, ll);

ll bbf(ll u, ll prev) {
    if (bb[u] != -1) return bb[u];
    vector<ll> c;
    for (ll x : gp[u]) {
        if (x != prev) c.push_back(x);
    }
    ll ret;
    if (c.size() == 0) {
        if (st[u] == 1) {
            ret = 0;
        } else {
            ret = 1e9;
        }
    } else if (c.size() == 1) {
        if (st[u] == 1) {
            ret = bbf(c[0], u);
        } else {
            ret = wwf(c[0], u) + 1;
        }
    } else {
        ll case1, case2;
        if (st[u] == 1) {
            case1 = bbf(c[0], u) + bbf(c[1], u);
            case2 = wwf(c[0], u) + wwf(c[1], u) + 2;
        } else {
            case1 = bbf(c[0], u) + wwf(c[1], u) + 1;
            case2 = wwf(c[0], u) + bbf(c[1], u) + 1;
        }
        ret = min(case1, case2);
    }
    return bb[u] = ret;
}

ll wwf(ll u, ll prev) {
    if (ww[u] != -1) return ww[u];
    vector<ll> c;
    for (ll x : gp[u]) {
        if (x != prev) c.push_back(x);
    }
    ll ret;
    if (c.size() == 0) {
        if (st[u] == 1) {
            ret = 1e9;
        } else {
            ret = 0;
        }
    } else if (c.size() == 1) {
        if (st[u] == 1) {
            ret = bwf(c[0], u) + 1;
        } else {
            ret = wbf(c[0], u);
        }
    } else {
        ll case1, case2;
        if (st[u] == 1) {
            case1 = bwf(c[0], u) + wbf(c[1], u) + 1;
            case2 = wbf(c[0], u) + bwf(c[1], u) + 1;
        } else {
            case1 = bwf(c[0], u) + bwf(c[1], u);
            case2 = wbf(c[0], u) + wbf(c[1], u) + 2;
        }
        ret = min(case1, case2);
    }
    return ww[u] = ret;
}

ll bwf(ll u, ll prev) {
    if (bw[u] != -1) return bw[u];
    vector<ll> c;
    for (ll x : gp[u]) {
        if (x != prev) c.push_back(x);
    }
    ll ret;
    if (c.size() == 0) {
        if (st[u] == 1) {
            ret = 0;
        } else {
            ret = 1e9;
        }
    } else if (c.size() == 1) {
        if (st[u] == 1) {
            ret = wbf(c[0], u);
        } else {
            ret = bwf(c[0], u) + 1;
        }
    } else {
        ll case1, case2;
        if (st[u] == 1) {
            case1 = wbf(c[0], u) + wbf(c[1], u);
            case2 = bwf(c[0], u) + bwf(c[1], u) + 2;
        } else {
            case1 = bwf(c[0], u) + wbf(c[1], u) + 1;
            case2 = wbf(c[0], u) + bwf(c[1], u) + 1;
        }
        ret = min(case1, case2);
    }
    return bw[u] = ret;
}

ll wbf(ll u, ll prev) {
    if (wb[u] != -1) return wb[u];
    vector<ll> c;
    for (ll x : gp[u]) {
        if (x != prev) c.push_back(x);
    }
    ll ret;
    if (c.size() == 0) {
        if (st[u] == 1) {
            ret = 1e9;
        } else {
            ret = 0;
        }
    } else if (c.size() == 1) {
        if (st[u] == 1) {
            ret = wwf(c[0], u) + 1;
        } else {
            ret = bbf(c[0], u);
        }
    } else {
        ll case1, case2;
        if (st[u] == 1) {
            case1 = bbf(c[0], u) + wwf(c[1], u) + 1;
            case2 = wwf(c[0], u) + bbf(c[1], u) + 1;
        } else {
            case1 = wwf(c[0], u) + wwf(c[1], u) + 2;
            case2 = bbf(c[0], u) + bbf(c[1], u);
        }
        ret = min(case1, case2);
    }
    return wb[u] = ret;
}

void solve() {
    cin >> n;
    gp = vector<vector<ll>>(n);
    st = vector<ll>(n);
    bb = wb = bw = ww = vector<ll>(n, -1);
    for (ll i = 1; i < n; i++) {
        ll u, v;
        cin >> u >> v;
        u--, v--;
        gp[u].push_back(v);
        gp[v].push_back(u);
    }
    for (ll& x : st) cin >> x, x = !x;
    ll ans = 1e9;
    for (ll u = 0; u < n; u++) {
        if (gp[u].size() != 3) {
            ans = min(wwf(u, -1) + 1, bbf(u, -1));
            break;
        }
    }
    if (ans >= 1e9) cout << "impossible" << endl;
    else cout << ans << endl;
}

int main() {
    //cin.tie(NULL); ios_base::sync_with_stdio(false);
    //int t; cin >> t; while (t--)
        solve();
}

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