Submission #783987

#	Time	Username	Problem	Language	Result	Execution time	Memory
783987		kebine	The Xana coup (BOI21_xanadu)	C++17	100 / 100	99 ms	18036 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,cur[100005];
vector <ll> al[100005];
ll vis[100005];
ll dp[100005][2][2];
void dfs(ll node){
    vis[node]=1;
    if (cur[node]==1){
        dp[node][1][0]+=1;
        dp[node][0][1]+=0;
        dp[node][0][0]+=1e9;
        dp[node][1][1]+=1e9;
    }
    else{
        dp[node][1][0]+=1e9;
        dp[node][0][1]+=1e9;
        dp[node][0][0]+=0;
        dp[node][1][1]+=1;
    }
    for (auto u:al[node]){
        if (vis[u]!=1){
            vis[u]=1;
            dfs(u);
            ll x=dp[node][0][0], y=dp[node][0][1];
            dp[node][0][0]=min(x+dp[u][0][0],y+dp[u][1][0]);
            dp[node][0][1]=min(y+dp[u][0][0],x+dp[u][1][0]);
            ll a=dp[node][1][0],b=dp[node][1][1];
            dp[node][1][0]=min(a+dp[u][0][1],b+dp[u][1][1]);
            dp[node][1][1]=min(b+dp[u][0][1],a+dp[u][1][1]);
        }
    }
}
int main(){
    cin>>n;
    for (int i=1;i<n;i++){
        ll a,b;
        cin>>a>>b;
        al[a].push_back(b);
        al[b].push_back(a);
    }
    for (int i=1;i<=n;i++){
        cin>>cur[i];
    }
    dfs(1);
    ll ans=min(dp[1][0][0],dp[1][1][0]);
    if (ans>n) cout<<"impossible";
    else cout<<ans;
}

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