Submission #598156

#	Time	Username	Problem	Language	Result	Execution time	Memory
598156		urosk	The Xana coup (BOI21_xanadu)	C++14	100 / 100	79 ms	18860 KiB

xanadu

#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;

#define maxn 100005
ll n;
vector<ll> g[maxn];
ll dp[maxn][2][2];
ll a[maxn];
void dfs(ll u,ll par){
    if(a[u]==1){
        dp[u][0][1] = 1;
        dp[u][0][0] = n+1;
        dp[u][1][0] = 0;
        dp[u][1][1] = n+1;
    }else{
        dp[u][0][0] = 0;
        dp[u][0][1] = n+1;
        dp[u][1][0] = n+1;
        dp[u][1][1] = 1;
    }
    ll sum = 0;
    for(ll s : g[u]){
        if(s==par) continue;
        dfs(s,u);
        for(ll k = 0;k<2;k++){
            ll dp0 = dp[u][0][k];
            ll dp1 = dp[u][1][k];
            dp[u][0][k] = min(dp0 + dp[s][k][0],dp1 + dp[s][k][1]);
            dp[u][1][k] = min(dp0 + dp[s][k][1],dp1 + dp[s][k][0]);
        }
    }
}
int main(){
	daj_mi_malo_vremena
    cin >> n;
    for(ll i = 1;i<=n-1;i++){
        ll x,y; cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    for(ll i = 1;i<=n;i++) cin >> a[i];
    dfs(1,1);
    ll ans = min(dp[1][0][1],dp[1][0][0]);
    if(ans>=n+1) cout<<"impossible"<<endl;
    else cout<<ans<<endl;
	return 0;
}
/*
5
1 2
1 3
2 4
2 5
0 1 0 1 1

*/

Compilation message (stderr)

xanadu.cpp: In function 'void dfs(long long int, long long int)':
xanadu.cpp:37:8: warning: unused variable 'sum' [-Wunused-variable]
   37 |     ll sum = 0;
      |        ^~~

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