Submission #1090272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090272		m5588ohammed	The Xana coup (BOI21_xanadu)	C++14	100 / 100	58 ms	25192 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
vector <int> v[100001];
int dp[100001][2][2],arr[100001];
void solve(int i,int last,int c,int u){
    if(dp[i][c][u]!=-1) return;
    int num=arr[i];
    if(min(c,u)==0&&max(c,u)==1) num^=1;
    if(v[i].size()==1&&i!=1){
        if(num==1) dp[i][c][u]=1e6;
        else dp[i][c][u]=u;
        return;
    }
    vector <int> ans;
    int sum=u;
    for(int j:v[i]){
        if(j!=last){
            if(u==1){
                solve(j,i,1,0);
                solve(j,i,1,1);
                sum+=dp[j][1][0];
                ans.push_back({dp[j][1][1]-dp[j][1][0]});
            }
            else{
                solve(j,i,0,0);
                solve(j,i,0,1);
                sum+=dp[j][0][0];
                ans.push_back({dp[j][0][1]-dp[j][0][0]});
            }
        }
    }
    sort(ans.begin(),ans.end());
    reverse(ans.begin(),ans.end());
    if(num==1){
        sum+=ans.back();
        ans.pop_back();
    }
    while(ans.size()>1){
        int a=ans.back();
        ans.pop_back();
        int b=ans.back();
        ans.pop_back();
        if(a+b>=0) break;
        sum+=a+b;
    }
    dp[i][c][u]=sum;
    return;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    memset(dp,-1,sizeof dp);
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=1;i<=n;i++) cin>>arr[i];
    solve(1,0,0,0);
    solve(1,0,0,1);
    int a=min(dp[1][0][0],dp[1][0][1]);
    if(a>=1e6) cout<<"impossible"<<endl;
    else cout<<a<<endl;
    return 0;
}

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