Submission #1022824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022824		gyg	The Xana coup (BOI21_xanadu)	C++17	100 / 100	101 ms	28452 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const int MAX_N = 1e5 + 5;
const lint INF = 1e9;

int n;
array<vector<int>, MAX_N> adj;
array<bool, MAX_N> a;

array<vector<int>, MAX_N> children;
void dfs1(int u = 1, int par = -1) {
    for (int v : adj[u]) 
        if (v != par) children[u].push_back(v), dfs1(v, u);
}

array<array<array<lint, 2>, 2>, MAX_N> dp1;
void dfs2(int u = 1) {
    for (int v : children[u]) dfs2(v);

    for (bool state : {false, true}) {
        for (bool toggle : {false, true}) {
            vector<array<lint, 2>> dp2(children[u].size() + 5);
            dp2[0][1] = INF;

            for (int i = 1; i <= children[u].size(); i++) {
                int v = children[u][i - 1];
                for (bool parity : {false, true}) {
                    lint leave = dp1[v][a[v] ^ toggle][0] + dp2[i - 1][parity];
                    lint take = dp1[v][a[v] ^ toggle ^ 1][1] + 1 + dp2[i - 1][parity ^ 1];
                    dp2[i][parity] = min(leave, take);
                    // cout << u << " " << state << " " << toggle << " " << v << " " << parity << ": " << dp2[i][parity] << endl;
                }
            }
            
            dp1[u][state][toggle] = dp2[children[u].size()][state];
            // cout << u << " " << state << " " << toggle << ": " << dp1[u][state][toggle] << endl;
        }
    }
}

int main() {
    // freopen("xana.in", "r", stdin);
    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 u = 1; u <= n; u++) cin >> a[u];

    dfs1();
    dfs2();

    lint ans = min(dp1[1][a[1]][false], dp1[1][a[1] ^ 1][true] + 1);
    if (ans >= INF) cout << "impossible" << '\n';
    else cout << ans << '\n';
}

Compilation message (stderr)

xanadu.cpp: In function 'void dfs2(int)':
xanadu.cpp:26:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |             for (int i = 1; i <= children[u].size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~

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