Submission #987353

#	Time	Username	Problem	Language	Result	Execution time	Memory
987353		AlphaMale06	The Xana coup (BOI21_xanadu)	C++17	100 / 100	65 ms	15712 KiB

xanadu

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e5+3;
int dp[N][2][2];
int a[N];
vector<int> g[N];

void dfs(int v, int p){
    if(g[v].size()==1){
        dp[v][a[v]][0]=0;
        dp[v][1-a[v]][1]=1;
        dp[v][a[v]][1]=1e6;
        dp[v][1-a[v]][0]=1e6;
        return;
    }
    for(int to : g[v]){
        if(to!=p){
            dfs(to, v);
        }
    }
    int mn=0, par=a[v], mnadd=1e9;
    for(int to : g[v]){
        if(to==p)continue;
        if(dp[to][0][0]<dp[to][0][1]){
            mn+=dp[to][0][0];
            mnadd=min(mnadd, dp[to][0][1]-dp[to][0][0]);
        }
        else{
            mn+=dp[to][0][1];
            mnadd=min(mnadd, dp[to][0][0]-dp[to][0][1]);
            par++;
            par%=2;
        }
    }
    dp[v][par][0]=mn;
    dp[v][1-par][0]=mn+mnadd;
    mn=0, par=a[v], mnadd=1e9;
    for(int to : g[v]){
        if(to==p)continue;
        if(dp[to][1][0]<dp[to][1][1]){
            mn+=dp[to][1][0];
            mnadd=min(mnadd, dp[to][1][1]-dp[to][1][0]);
        }
        else{
            mn+=dp[to][1][1];
            mnadd=min(mnadd, dp[to][1][0]-dp[to][1][1]);
            par++;
            par%=2;
        }
    }
    dp[v][1-par][1]=mn+1;
    dp[v][par][1]=mn+mnadd+1;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i=0; i< n-1; i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1; i<=n; i++)cin >> a[i];
    int root=0;
    for(int i=1; i<=n; i++){
        if(g[i].size()>1)root=i;
    }
    dfs(root, root);
    int ans = min(dp[root][0][0], dp[root][0][1]);
    if(ans<=n)cout << ans << '\n';
    else cout << "impossible\n";
}

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