Submission #1272545

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272545		Rares	The Xana coup (BOI21_xanadu)	C++20	100 / 100	53 ms	15940 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN=1e5+10;
const int INF=1e9;

int n,a[MAXN],dp[2][2][MAXN];
vector <int> g[MAXN];
///everybody has to be 0
void dfs (int node, int prevn){
    bool ok=0;
    for (auto x:g[node]){
        if (x==prevn) continue;
        dfs (x,node);
        ok=1;
    }
    ///node is leaf
    if (ok==0){
        dp[a[node]][0][node]=0;
        dp[1-a[node]][1][node]=1;
        return;
    }
    ///if node is not using than all of his sons must be 0
    int s=0,nr=0,mind=INF;
    for (auto x:g[node]){
        if (x==prevn) continue;
        ///is x used or not
        if (dp[0][1][x]<dp[0][0][x]){
            s+=dp[0][1][x];
            nr++;
        }
        else{
            s+=dp[0][0][x];
        }
        if (dp[0][1][x]!=INF and dp[0][0][x]!=INF)
            mind=min (mind,abs (dp[0][1][x]-dp[0][0][x]));
    }
    dp[(nr+a[node])%2][0][node]=s;
    dp[(nr+a[node]+1)%2][0][node]=min (INF,s+mind);

    ///if node is used than all of his sons must be 1
    s=0,nr=0,mind=INF;
    for (auto x:g[node]){
        if (x==prevn) continue;
        if (dp[1][1][x]<dp[1][0][x]){
            s+=dp[1][1][x];
            nr++;
        }
        else{
            s+=dp[1][0][x];
        }
        if (dp[1][1][x]!=INF and dp[1][0][x]!=INF)
            mind=min (mind,abs (dp[1][1][x]-dp[1][0][x]));
    }
    ///I am pressing 1 so add 1

    dp[(nr+a[node]+1)%2][1][node]=s+1;
    dp[(nr+a[node])%2][1][node]=min (INF,s+mind+1);
}

signed main()
{
    ios_base::sync_with_stdio (false);
    cin.tie (nullptr);

    cin >>n;
    for (int i=1;i<n;++i){
        int x,y;
        cin >>x>>y;
        g[x].push_back (y);
        g[y].push_back (x);
    }
    for (int i=1;i<=n;++i){
        cin >>a[i];
        dp[0][0][i]=dp[0][1][i]=dp[1][0][i]=dp[1][1][i]=INF;
    }

    dfs (1,1);

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

    if (rez>=INF){
        cout <<"impossible";
    }
    else{
        cout <<rez;
    }
    return 0;
}

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