Submission #676405

#	Time	Username	Problem	Language	Result	Execution time	Memory
676405		c2zi6	The Xana coup (BOI21_xanadu)	C++14	10 / 100	136 ms	24732 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;
 
int n;
vector<vector<int>> gp;
vector<int> st;
 
vector<int> bb, wb, bw, ww;
int bbf(int, int);
int wbf(int, int);
int bwf(int, int);
int wwf(int, int);
 
int bbf(int u, int prev) {
    if (bb[u] != -1) return bb[u];
    vector<int> c;
    for (int x : gp[u]) {
        if (x != prev) c.push_back(x);
    }
    int 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 {
        int 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;
}
 
int wwf(int u, int prev) {
    if (ww[u] != -1) return ww[u];
    vector<int> c;
    for (int x : gp[u]) {
        if (x != prev) c.push_back(x);
    }
    int 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 {
        int 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;
}
 
int bwf(int u, int prev) {
    if (bw[u] != -1) return bw[u];
    vector<int> c;
    for (int x : gp[u]) {
        if (x != prev) c.push_back(x);
    }
    int 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 {
        int 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;
}
 
int wbf(int u, int prev) {
    if (wb[u] != -1) return wb[u];
    vector<int> c;
    for (int x : gp[u]) {
        if (x != prev) c.push_back(x);
    }
    int 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 {
        int 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<int>>(n);
    st = vector<int>(n);
    bb = wb = bw = ww = vector<int>(n, -1);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        gp[u].push_back(v);
        gp[v].push_back(u);
    }
    for (int& x : st) cin >> x, x = !x;
    int ans = 1e9;
    for (int 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