Submission #478584

#	Time	Username	Problem	Language	Result	Execution time	Memory
478584		Haruto810198	The Xana coup (BOI21_xanadu)	C++17	55 / 100	149 ms	30584 KiB

xanadu

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = 2147483647;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 100010;

int n;
int val[MAX];
vi edge[MAX];
vi ch[MAX];

int dp[MAX][2][2]; // dp[v][v is 1][parent of v is switched]

void dfs(int v, int pv){
    for(int i : edge[v]){
        if(i == pv) continue;
        ch[v].pb(i);
        dfs(i, v);
    }
}

void solve(int v){

    dp[v][0][0] = dp[v][0][1] = dp[v][1][0] = dp[v][1][1] = INF;

    for(int i : ch[v]){
        solve(i);
    }

    int sz = szof(ch[v]);
    FOR(mask, 0, (1<<sz) - 1, 1){

        vi state;
        FOR(i, 0, sz-1, 1){
            if(mask & (1<<i)) state.pb(1);
            else state.pb(0);
        }

        // dp[v][?][0] :
        // all childs = 0 -> do not flip v
        // pick dp[u][0][?] for all childs u

        int new_val_v = val[v];
        int dp_sum = 0;
        FOR(i, 0, sz-1, 1){
            int u = ch[v][i];
            new_val_v ^= state[i];
            dp_sum += dp[u][0][state[i]];
        }

        dp[v][new_val_v][0] = min(dp[v][new_val_v][0], dp_sum);

        // dp[v][?][1] :
        // all childs = 1 -> flip v
        // pick dp[u][1][?] for all childs u

        new_val_v = val[v];
        dp_sum = 0;
        FOR(i, 0, sz-1, 1){
            int u = ch[v][i];
            new_val_v ^= state[i];
            dp_sum += dp[u][1][state[i]];
        }

        // flip v : upd. new_val_v, dp_sum
        new_val_v ^= 1;
        dp_sum += 1;

        dp[v][new_val_v][1] = min(dp[v][new_val_v][1], dp_sum);

    }

}

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n;

    FOR(i, 1, n-1, 1){
        int u, v;
        cin>>u>>v;
        edge[u].pb(v);
        edge[v].pb(u);
    }

    FOR(i, 1, n, 1){
        cin>>val[i];
    }

    dfs(1, -1);
    solve(1);

    int res = min(dp[1][0][0], dp[1][0][1]);

    if(res < INF) cout<<res<<'\n';
    else cout<<"impossible"<<'\n';

    return 0;

}

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