Submission #755359

#	Time	Username	Problem	Language	Result	Execution time	Memory
755359		__Davit__	The Xana coup (BOI21_xanadu)	C++17	100 / 100	120 ms	16888 KiB

xanadu

#define _CRT_SECURE_NO_WARNINGS

#include <bits/stdc++.h>

#define ll long long
#define lld long double
#define ff first
#define ss second
#define pb push_back
#define vr(v) v.begin(),v.end()
#define rv(v) v.rbegin(),v.rend()
#define Code ios_base::sync_with_stdio(false);
#define By cin.tie(NULL);
#define Davit cout.tie(NULL);

using namespace std;

vector<vector<int>> gp;
vector<int> col;

const int INF = 1e6;
ll dp[100005][2][2];

void dfs(int u, int p) {

    for (auto x: gp[u]) {
        if (x != p)dfs(x, u);
    }

    if ((int) gp[u].size() == 1 && u != 0) {//leaves
        if (col[u]) {
            dp[u][0][0] = 0;
            dp[u][1][1] = 1;
            dp[u][0][1] = dp[u][1][0] = INF;
        } else {
            dp[u][0][0] = INF;
            dp[u][1][1] = INF;
            dp[u][1][0] = 1;
            dp[u][0][1] = 0;//we count it later (during merge)
        }
        return;
    }
    ll res = 0, cnt = 0, diff = INF;
    //dp[x][0/1][0]
    for (auto x: gp[u]) {
        if (x == p)continue;
        res += min(dp[x][0][0], dp[x][1][0]);
        if (dp[x][1][0] < dp[x][0][0])cnt++;
        diff = min(diff, abs(dp[x][0][0] - dp[x][1][0]));
    }
    dp[u][0][0] = res;
    if (col[u] == cnt % 2)dp[u][0][0] += diff;
    dp[u][0][1] = res;
    if (col[u] != cnt % 2)dp[u][0][1] += diff;

    res = 0, cnt = 0, diff = INF;
    for (auto x: gp[u]) {
        if (x == p)continue;
        res += min(dp[x][0][1], dp[x][1][1]);
        if (dp[x][1][1] < dp[x][0][1])cnt++;
        diff = min(diff, abs(dp[x][0][1] - dp[x][1][1]));
    }
    res++;
    dp[u][1][0] = res;
    if (col[u] != cnt % 2)dp[u][1][0] += diff;
    dp[u][1][1] = res;
    if (col[u] == cnt % 2)dp[u][1][1] += diff;

}

int main() {
    int n;
    cin >> n;
    gp.resize(n);
    col.resize(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        gp[u].pb(v);
        gp[v].pb(u);
    }
    for (int i = 0; i < n; i++)cin >> col[i], col[i] = !col[i];

    dfs(0, -1);

    ll res = min(dp[0][0][0], dp[0][1][0]);
    if (res > n) cout << "impossible\n";
    else cout << res << "\n";
}

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