제출 #1359082

#제출 시각아이디문제언어결과실행 시간메모리
1359082yc11The Xana coup (BOI21_xanadu)C++20
0 / 100
96 ms73580 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;

int yaye(vector<int> a, vector<int> b){
    vector<int> c;
        for (int i = 0;i<a.size();i++){
        c.push_back(a[i]-b[i]);
    }
    sort(c.begin(),c.end());
    int c1 = 0;
    int ans = 0;
    while (c1!=c.size() and c[c1]<=0) {ans+=c[c1];c1++;}
    if (c1%2==1){
        if (c1!=c.size()) ans = min(ans+c[c1],ans-c[c1-1]);
        else ans = ans-c[c1-1];
    }
    for (int i = 0;i<b.size();i++) ans+=b[i];
    return ans;

}
int yayo(vector<int> a, vector<int> b){
    vector<int> c;
        for (int i = 0;i<a.size();i++){
        c.push_back(a[i]-b[i]);
    }
    sort(c.begin(),c.end());
    int c1 = 0;
    int ans = 0;
    while (c1!=c.size() and c[c1]<=0) {ans+=c[c1];c1++;}
    if (c1%2==0){
        if (c1!=c.size() and c1!=0) ans = min(ans+c[c1],ans-c[c1-1]);
        else if (c1==c.size()) ans = ans-c[c1-1];
        else ans=ans+c[c1];

    }
    for (int i = 0;i<b.size();i++) ans+=b[i];

    return ans;

}
void dfs(int x, int p){
    if (n1[x].size()==1 and p!=-1){
        if (n2[x]==1){
            dp[x]=make_pair(make_pair(1e9,0),make_pair(1,1e9));
        }
        else{
            dp[x] = make_pair(make_pair(1,1e9),make_pair(1e9,0));
        }
        return;
    }
    vector<int> one;
    vector<int> two;
    vector<int> three;
    vector<int> four;
    for (int i = 0;i<n1[x].size();i++){
        if (n1[x][i]==p) continue;
        dfs(n1[x][i],x);
        one.push_back(dp[n1[x][i]].first.first);
        two.push_back(dp[n1[x][i]].first.second);
        three.push_back(dp[n1[x][i]].second.first);
        four.push_back(dp[n1[x][i]].second.second);
    }


    if (n2[x]==1){
        dp[x] = make_pair(make_pair(yayo(one,two)+1,yaye(three,four)),make_pair(yaye(one,two)+1,yayo(three,four)));
    }
    else{
        dp[x] = make_pair(make_pair(yaye(one,two)+1,yayo(three,four)),make_pair(yayo(one,two)+1,yaye(three,four)));
    }
    
}
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.first,dp[0].second.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...