Submission #939581

#	Time	Username	Problem	Language	Result	Execution time	Memory
939581		LucaIlie	The Xana coup (BOI21_xanadu)	C++17	100 / 100	98 ms	21332 KiB

xanadu

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

struct DP {
    int dp[2][2];

    DP operator+( const DP &b ) const {
        DP a = *this;
        DP c;

        for ( int s = 0; s < 2; s++ ) {
            for ( int t = 0; t < 2; t++ )
                c.dp[s][t] = INF;
        }

        for ( int sa = 0; sa < 2; sa++ ) {
            for ( int ta = 0; ta < 2; ta++ ) {
                for ( int sb = 0; sb < 2; sb++ ) {
                    for ( int tb = 0; tb < 2; tb++ ) {
                        if ( sb ^ ta == 1 )
                            continue;
                        c.dp[sa ^ tb][ta] = min( c.dp[sa ^ tb][ta], a.dp[sa][ta] + b.dp[sb][tb] );
                    }
                }
            }
        }

        return c;
    }
};

const int MAX_N = 1e5;
bool isTurnedOn[MAX_N + 1];
DP minSwitches[MAX_N + 1];
vector <int> adj[MAX_N + 1];

void dfs( int u, int p ) {
    for ( int s = 0; s < 2; s++ ) {
        for ( int t = 0; t < 2; t++ )
            minSwitches[u].dp[s][t] = (s ^ t == isTurnedOn[u] ? t : INF);
    }
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        dfs( v, u );
        minSwitches[u] = minSwitches[u] + minSwitches[v];
    }

    /*printf( "%d\n", u );
    printf( "%d %d\n", minSwitches[u].dp[0][0], minSwitches[u].dp[0][1] );
    printf( "%d %d\n", minSwitches[u].dp[1][0], minSwitches[u].dp[1][1] );*/
}

int main() {
    int n;

    cin >> n;
    for ( int i = 0; i < n - 1; i++ ) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back( v );
        adj[v].push_back( u );
    }
    for ( int v = 1; v <= n; v++ )
        cin >> isTurnedOn[v];

    dfs( 1, 0 );

    int ans = min( minSwitches[1].dp[0][0], minSwitches[1].dp[0][1] );
    if ( ans <= n )
        cout << ans;
    else
        cout << "impossible\n";

    return 0;
}

Compilation message (stderr)

xanadu.cpp: In member function 'DP DP::operator+(const DP&) const':
xanadu.cpp:23:38: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   23 |                         if ( sb ^ ta == 1 )
      |                                   ~~~^~~~
xanadu.cpp: In function 'void dfs(int, int)':
xanadu.cpp:43:46: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   43 |             minSwitches[u].dp[s][t] = (s ^ t == isTurnedOn[u] ? t : INF);
      |                                            ~~^~~~~~~~~~~~~~~~

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