Submission #1026038

#TimeUsernameProblemLanguageResultExecution timeMemory
1026038warrennThe Xana coup (BOI21_xanadu)C++17
5 / 100
63 ms16728 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long 

const int maxn=1e5+5;
int n;
vector<int>adj[maxn];
int dp[maxn][2][2]; // idx,nyala,toggle
bool vis[maxn];
bool on[maxn];

void dfs(int cur){
    vis[cur]=true;
    
    if(on[cur]){
        dp[cur][1][0]=0;
        dp[cur][0][1]=1;
    }
    else{
        dp[cur][0][0]=0;
        dp[cur][1][1]=1;
    }

    for(auto r : adj[cur]){
        if(vis[r])continue;
        dfs(r);
        // jangan toggle
        int q=dp[cur][0][0]; int w=dp[cur][1][0];

        dp[cur][0][0]=min(q+dp[r][0][0],w+dp[r][0][1]);
        dp[cur][1][0]=min(q+dp[r][0][1],w+dp[r][0][0]);

        q=dp[cur][0][1]; w=dp[cur][1][1];
        dp[cur][0][1]=min(q+dp[r][1][0],w+dp[r][1][1]);
        dp[cur][1][1]=min(w+dp[r][1][0],q+dp[r][1][1]);
    }
}

signed main(){
    cin>>n;
    for(int d=1;d<=n-1;d++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int d=1;d<=n;d++){
        for(int e=0;e<=1;e++){
            for(int f=0;f<=1;f++){
                dp[d][e][f]=1e18;
             }
        }
    }
    for(int d=1;d<=n;d++){
        cin>>on[d];
    }
    dfs(1);
    if(min(dp[1][0][0],dp[1][0][1])==1e18){
        cout<<"impossible"<<endl;
    }
    else{
        cout<<min(dp[1][0][0],dp[1][0][1])<<endl;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...