Submission #478586

#	Time	Username	Problem	Language	Result	Execution time	Memory
478586		Haruto810198	The Xana coup (BOI21_xanadu)	C++17	100 / 100	146 ms	24312 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]);

    //int new_val_v = val[v];
    //int dp_sum = 0;
    int opt[2], n_opt[2]; // dp_sum if new_val_v == 0 / 1

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

    opt[val[v]] = 0;
    opt[val[v] ^ 1] = INF;

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

    dp[v][0][0] = min(dp[v][0][0], opt[0]);
    dp[v][1][0] = min(dp[v][1][0], opt[1]);

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

    opt[val[v]] = 0;
    opt[val[v] ^ 1] = INF;

    FOR(i, 0, sz-1, 1){
        int u = ch[v][i];
        n_opt[0] = min(opt[0] + dp[u][1][0], opt[1] + dp[u][1][1]);
        n_opt[1] = min(opt[1] + dp[u][1][0], opt[0] + dp[u][1][1]);
        opt[0] = n_opt[0];
        opt[1] = n_opt[1];
    }

    // flip v : upd. new_val_v, dp_sum
    //new_val_v ^= 1;
    //dp_sum += 1;
    swap(opt[0], opt[1]);
    opt[0] += 1;
    opt[1] += 1;

    dp[v][0][1] = min(dp[v][0][1], opt[0]);
    dp[v][1][1] = min(dp[v][1][1], opt[1]);

}

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: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40
• Subtask 5: 30 / 30