제출 #1359162

#제출 시각아이디문제언어결과실행 시간메모리
1359162yc11The Xana coup (BOI21_xanadu)C++20
0 / 100
51 ms17512 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int> > n1;
vector<pair<pair<int,int>, pair<int,int> > > dp;
vector<int> n2;
void dfs(int x, int p){
    if (n2[x]==0) dp[x] = make_pair(make_pair(1,1e9),make_pair(1e9,0));
    else dp[x] = make_pair(make_pair(1e9,1),make_pair(0,1e9));
    for (int i = 0;i<n1[x].size();i++){
            if (n1[x][i]==p) continue;
    dfs(n1[x][i],x);
    pair<pair<int,int> , pair<int,int> > yay;
        yay.first.first = min(dp[x].first.second+dp[n1[x][i]].first.first,dp[x].first.first+dp[n1[x][i]].second.first);
        yay.first.second = min(dp[x].first.second+dp[n1[x][i]].second.first,dp[x].first.first+dp[n1[x][i]].first.first);
        yay.second.first=  min(dp[x].second.first+dp[n1[x][i]].second.second,dp[x].second.second+dp[n1[x][i]].first.second);
        yay.second.second = min(dp[x].second.second+dp[n1[x][i]].second.second,dp[x].second.first+dp[n1[x][i]].first.second);
        dp[x] = yay;
        
    }
   
}
signed main(){
    int n;
    cin>>n;
    n1.resize(n);
    dp.resize(n);
    n2.resize(n);
    for (int i = 0;i<n-1;i++){
        int a,b,c;
        cin>>a>>b;
        n1[a-1].push_back(b-1);
        n1[b-1].push_back(a-1);
    }
    for (int i = 0;i<n;i++) cin>>n2[i];
    dfs(0,-1);
    int x = min(dp[0].second.second,dp[0].first.second);

    if (x>=1e9) cout<<"Impossible";
    else cout<<x;
}
#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...