oj.uz

Submission #676410

# Submission time Handle Problem Language Result Execution time Memory
676410 2022-12-30T19:59:18 Z c2zi6 The Xana coup (BOI21_xanadu) C++14
10 / 100
 152 ms 25384 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 25168 KB Output is correct
2 Correct 114 ms 24848 KB Output is correct
3 Correct 152 ms 25288 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 25200 KB Output is correct
2 Correct 107 ms 24800 KB Output is correct
3 Correct 111 ms 25384 KB Output is correct
4 Correct 114 ms 9464 KB Output is correct
5 Correct 122 ms 10336 KB Output is correct
6 Correct 120 ms 10644 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 33 ms 3668 KB Output is correct
9 Correct 119 ms 10144 KB Output is correct
10 Correct 127 ms 10316 KB Output is correct
11 Correct 130 ms 11128 KB Output is correct
12 Correct 130 ms 11404 KB Output is correct
13 Incorrect 108 ms 10204 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -