Submission #762297

#	Time	Username	Problem	Language	Result	Execution time	Memory
762297		Sharky	The Xana coup (BOI21_xanadu)	C++17	100 / 100	48 ms	23564 KiB

xanadu

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

#define int long long
const int maxn = 1E5+5;
const int INF = 1E9;
int n, dp[maxn][2][2], b[maxn]; // colours AFTER flipping, times flipped
bool cn[maxn][2][2];
vector<int> adj[maxn];

void dfs(int u, int p) {
    // cout << u << " " << p << endl;
    for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) {
        dp[u][i][j] = INF;
    }
    // int one[2][2];
    // for (int i = 0; i < 2; i++) {
    //     for (int j = 0; j < 2; j++) {
    //         cn[u][i][j] = (b[u] == (i ^ j));
    //         one[i][j] = 0;
    //     }
    // }
    int child = 0;
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        child++;
        // cn[u][0][0] = (cn[u][0][0] & cn[v][0][0]);
        // cn[u][1][0] = (cn[u][1][0] & cn[v][0][0]);
        // cn[u][0][1] = (cn[u][0][1] & cn[v][1][0]);
        // cn[u][1][1] = (cn[u][1][1] & cn[v][1][0]);
    }
    // for (int i = 0; i < 2; i++) {
    //     for (int j = 0; j < 2; j++) {
    //         if (!cn[u][i][j]) continue;
    //         for (int v : adj[u]) {
    //             if (v == p) continue;
    //             dp[u][i][j] += dp[v][j][0] + j;
    //         }
    //     }
    // }

    for (int k = 0; k < 2; k++) {     
        int i = 0, one[2][2];
        one[0][0] = one[1][0] = 0;
        one[0][1] = one[1][1] = INF;
        for (int v : adj[u]) {
            if (v == p) continue;
            one[i][0] = min({one[i ^ 1][1] + dp[v][k][1], one[i ^ 1][0] + dp[v][k][0]});
            one[i][1] = min({one[i ^ 1][0] + dp[v][k][1], one[i ^ 1][1] + dp[v][k][0]});
            // cout << "ones: " << one[i][0] << " " << one[i][1] << "\n";
            i = i ^ 1;
        }
        // cout << (i ^ 1) << " " << k << " " << one[0][0] << " " << one[0][1] << " " << one[1][0] << " " << one[1][1] << "\n";
        // cout << (i ^ 1) << " " << (b[u] ^ k) << endl;
        dp[u][b[u] ^ k][k] = min(dp[u][b[u] ^ k][k], one[i ^ 1][0]);
        dp[u][b[u] ^ 1 ^ k][k] = min(dp[u][b[u] ^ 1 ^ k][k], one[i ^ 1][1]);
    }
    dp[u][0][1]++, dp[u][1][1]++;
    // for (int i = 0; i < 2; i++) {
    //     for (int j = 0; j < 2; j++) {
    //         if (b[u] != (i ^ j)) dp[u][i][j] = INF;
    //     }
    // }
    // cout << u << endl;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            // cout << ((i == 0) ? "off " : "on ") <<((j == 0) ? "noflip " : "flip ") << dp[u][i][j] << ' ';
        }
        // cout << '\n';
    }
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) cin >> b[i];
    dfs(1, 0);
    int mn = 1E18;
    for (int j = 0; j < 2; j++) {
        mn = min(mn, dp[1][0][j]);
    }
    if (mn > n) cout << "impossible\n";
    else cout << mn << endl;
}

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