Submission #1307669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307669		shivenbhargava	The Xana coup (BOI21_xanadu)	C++20	100 / 100	36 ms	15260 KiB

xanadu

#include "bits/stdc++.h"
using namespace std;

const int MAXN = 100005;
const int INF = 2147483647;

int yes[MAXN],no[MAXN],diffyes[MAXN],diffno[MAXN];
vector<int> graph[MAXN];
bool states[MAXN];
int cur,total,mindiff; bool possible;

void dfs(int u, int v) {
    for (int i : graph[u]) if (i != v) dfs(i,u);
    cur = 0, total = 0, mindiff = INF; possible = true;
    for (int i : graph[u]) {
        if (i == v) continue;
        if (yes[i]<no[i]) cur++;
        if (min(yes[i],no[i]) == INF) { possible = false; break; }
        total+=min(yes[i],no[i]);
        if (max(yes[i],no[i]) != INF) mindiff = min(mindiff,abs(yes[i]-no[i]));
    }
    if (possible) {
        if (cur%2 == states[u]) {
            no[u] = total;
            if (mindiff!=INF) diffno[u] = total+mindiff;
        } else {
            diffno[u] = total;
            if (mindiff!=INF) no[u] = total+mindiff;
        }
    }
    cur = 1, total = 1, mindiff = INF; possible = true;
    for (int i : graph[u]) {
        if (i == v) continue;
        if (diffyes[i]<diffno[i]) cur++;
        if (min(diffyes[i],diffno[i]) == INF) { possible = false; break; }
        total+=min(diffyes[i],diffno[i]);
        if (max(diffyes[i],diffno[i]) != INF) mindiff = min(mindiff,abs(diffyes[i]-diffno[i]));
    }
    if (possible) {
        if (cur%2 == states[u]) {
            yes[u] = total;
            if (mindiff!=INF) diffyes[u] = total+mindiff;
        } else {
            diffyes[u] = total;
            if (mindiff!=INF) yes[u] = total+mindiff;
        }
    }
}

int main() {
    #ifdef LOCAL
    freopen("submission/input.in", "r", stdin);
    freopen("submission/output.out", "w", stdout);
    #else
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif

    int n; cin >> n;
    for (int i = 1; i<n; i++) { int x,y; cin >> x >> y; graph[x].push_back(y); graph[y].push_back(x); }
    for (int i = 1; i<=n; i++) cin >> states[i];
    fill(yes,yes+MAXN,INF); fill(no,no+MAXN,INF); fill(diffyes,diffyes+MAXN,INF); fill(diffno,diffno+MAXN,INF);
    dfs(1,0);
    int x = min(yes[1],no[1]);
    if (x == INF) cout << "impossible\n";
    else cout << x << '\n';
    return 0;
}

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