제출 #1026048

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1026048		warrenn	The Xana coup (BOI21_xanadu)	C++17	100 / 100	69 ms	16724 KiB

xanadu

#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]=1e15;
             }
        }
    }
    for(int d=1;d<=n;d++){
        cin>>on[d];
    }
    dfs(1);
    if(min(dp[1][0][0],dp[1][0][1])>n){
        cout<<"impossible"<<endl;
    }
    else{
        cout<<min(dp[1][0][0],dp[1][0][1])<<endl;
    }
}

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