oj.uz

Submission #676405

# Submission time Handle Problem Language Result Execution time Memory
676405 2022-12-30T18:13:18 Z c2zi6 The Xana coup (BOI21_xanadu) C++14
10 / 100
 136 ms 24732 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;
 
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.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 136 ms 23216 KB Output is correct
2 Correct 121 ms 24304 KB Output is correct
3 Correct 125 ms 24652 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 23276 KB Output is correct
2 Correct 123 ms 24284 KB Output is correct
3 Correct 124 ms 24732 KB Output is correct
4 Incorrect 111 ms 8052 KB Output isn't correct
5 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 -