Submission #960993

#	Time	Username	Problem	Language	Result	Execution time	Memory
960993		Gr1sen	The Xana coup (BOI21_xanadu)	C++17	100 / 100	85 ms	17004 KiB

xanadu

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>

using namespace std;

#define vi vector<int>
#define vvi vector<vi>

int inf = 1e8;

struct point {
    int a = inf, b = inf, c = inf, d = inf; // no flip on, flip on, no flip off, flip off
};

vi O;
vvi Adj;

point oink(int p, int dfp) {
    if (Adj[p].size() == 1 && Adj[p][0] == dfp) {
        if (O[p]) return {0, inf, inf, 1};
        return {inf, 1, 0, inf};
    }
    bool q = 1;
    point l;
    for (auto i : Adj[p]) { 
        if (i == dfp) continue;
        point o = oink(i, p);
        //cerr << "o: " << o.a << ", " << o.b << ", " << o.c << ", " << o.d << "; p:" << i+1 << endl;
        if (q) {
            l = o;
            q = 0;
            continue;
        }
        point ln;
        ln.a = min(min(l.a + o.a, l.b + o.b), inf);
        ln.b = min(min(l.a + o.b, l.b + o.a), inf);
        ln.c = min(min(l.c + o.c, l.d + o.d), inf);
        ln.d = min(min(l.c + o.d, l.d + o.c), inf);
        l = ln;
    }
    //cerr << l.a << " " << l.b << " " << l.c << " " << l.d << "; p: " << p+1 << "; dfp: " << dfp+1 << endl;
    if (O[p]) return {l.c, l.b+1, l.d, l.a+1};
    return {l.d, l.a+1, l.c, l.b+1};
}

int main() {
    ios::sync_with_stdio(); cin.tie(0);
    int n; cin >> n;
    Adj.resize(n);
    for (int i = 0; i < n-1; i++) {
        int a, b; cin >> a >> b; a--; b--;
        Adj[a].push_back(b);
        Adj[b].push_back(a);
    }
    O.resize(n);
    for (auto &i : O) cin >> i;
    point ans = oink(0, -1);
    int a = min(ans.c, ans.d);
    if (a >= inf) cout << "impossible\n";
    else cout << a << "\n";
}

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