제출 #648132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
648132		dooompy	The Xana coup (BOI21_xanadu)	C++17	0 / 100	65 ms	21452 KiB

xanadu

#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

vector<int> adj[100005];
int status[100005];
pair<int, ll> cost[100005][2]; // 0 off, 1 on

void dfs(int node, int par = -1) {
    int child = 0;

    ll noct = 0, nocost = 0, onct = 0, oncost = 0;

    for (auto nxt : adj[node]) {
        if (nxt == par) continue;

        dfs(nxt, node);
        child++;

        noct += cost[nxt][0].first;
        nocost += cost[nxt][0].second;

        onct += cost[nxt][1].first;
        oncost += cost[nxt][1].second;
    }

    if (child == 0) {
        cost[node][status[node]] = {0, 0};
        cost[node][1 - status[node]] = {1, 1};
        return;
    }

    // dont place on this block

    {
        int curstat = status[node] ^ (noct % 2);

        if (curstat == 0) {
            cost[node][0].first = 0;
            cost[node][0].second = nocost;
        } else {
            cost[node][1].first = 0;
            cost[node][1].second = nocost;
        }
    }

    // place on this block

    {
        int curstat = status[node] ^ (onct % 2);

        if (curstat == 0) {
            cost[node][1].first = 1;
            cost[node][1].second = oncost + 1;
        } else {
            cost[node][0].first = 1;
            cost[node][0].second = oncost + 1;
        }
    }

//
//    if (status[node] == 0) {
//        int curstat = status[node] ^ (noct % 2);
//
//        if (curstat == 1) {
//            // impossible
//            cost[node][0].second = 1e9;
//        } else {
//            cost[node][0].first = 0;
//            cost[node][0].second = nocost;
//        }
//    } else {
//        int curstat = status[node] ^ (onct % 2);
//
//        if (curstat == 0) {
//            // impossible
//            cost[node][1].second = 1e9;
//        } else {
//            cost[node][0].first = 0;
//            cost[node][0].second = nocost;
//        }
//    }
//
//    int curstat = status[node] ^ (noct % 2);
//    int req = bool(curstat != 1);
//    cost[node][1].first = req;
//    cost[node][1].second = nocost + req;
//
//    curstat = status[node] ^ (onct % 2);
//    req = bool(curstat != 0);
//    cost[node][0].first = req;
//    cost[node][0].second = oncost + req;

}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int n; cin >> n;
    for (int i = 0; i < n-1; i++) {
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    for (int i = 1; i <= n; i++) cin >> status[i];

    fill(&cost[0][0], &cost[0][0] + sizeof(cost) / sizeof(cost[0][0]), pair<int, ll> {0, 1e9});
    dfs(1);

    if (cost[1][0].second >= 1e9) cout << "impossible" << endl;
    else cout << cost[1][0].second << endl;
}

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