Submission #1039455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039455		Maite_Morale	The Xana coup (BOI21_xanadu)	C++17	0 / 100	45 ms	51024 KiB

xanadu

#include<bits/stdc++.h>
#define F first
#define S second
#define MAX 500005
#define oo 1e18
#define mod 1000000007
#define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0);
using namespace std;
typedef long long ll;
#define pll pair<ll , ll>
#define vll vector<ll>
#define vvll vector<vll>
#define vpll vector<pll>
 
ll t,n,m,k,c,a[MAX],dp[5][5][MAX],cost[5][5][MAX];
vll v[MAX];
ll dfs(ll x,ll y){
    ll h[2][2]={{0,0},{0,0}},sp[2]={0,0},si[2]={-1,-1};
    vll op[2]={{},{}};
    ll c=0,b=0;
    for( auto w : v[x]){
        if(w==y)continue;
        dfs(w,x);
        for(int i=0;i<2;i++){
            if(dp[0][i][w]==1){
                h[0][i]++;sp[i]+=cost[0][i][w];
                if(dp[1][i][w]==1)op[i].push_back(-(cost[1][i][w]-cost[0][i][w]));
            }else if(dp[1][i][w]==1){h[1][i]++;sp[i]+=cost[1][i][w];}
        }
        c++;
    }
    for(int i=0;i<2;i++){
        if(op[i].size()==0)continue;
        si[i]=sp[i];
        sort(op[i].begin(),op[i].end());
        si[i]-=op[i][0];
        for(int j=1;j+1<op[i].size();j++){
            if(-op[i][j]-op[i][j+1]>0){
                if(j%2==1)si[i]+=-op[i][j]-op[i][j+1];
                else      sp[i]+=-op[i][j]-op[i][j+1]; 
            }
            else break;
        }
    }
    b=0;
    //cout<<h[0][0]<<" "<<h[1][0]<<" "<<h[0][1]<<" "<<h[1][1]<<"\n";
    if(h[0][0]+h[1][0]==c && (h[1][0]%2==0 || op[0].size()>0))b=1;
    dp[0][0^a[x]][x]=b;
    cost[0][0^a[x]][x]=oo;
    if(b==1){
        if(h[1][0]%2==0)cost[0][0^a[x]][x]=sp[0];
        else            cost[0][0^a[x]][x]=si[0];
    }
    b=0;
    if(h[0][0]+h[1][0]==c && (h[1][0]%2==1 || op[0].size()>0))b=1;
    dp[0][1^a[x]][x]=b;
    cost[0][1^a[x]][x]=oo;
    if(b==1){
        if(h[1][0]%2==1)cost[0][1^a[x]][x]=sp[0];
        else            cost[0][1^a[x]][x]=si[0];
    }
    b=0;
    if(h[0][1]+h[1][1]==c && (h[1][1]%2==0 || op[1].size()>0))b=1;
    dp[1][1^a[x]][x]=b;
    cost[1][1^a[x]][x]=oo;
    if(b==1){
        if(h[1][0]%2==0)cost[1][1^a[x]][x]=sp[0]+1;
        else            cost[1][1^a[x]][x]=si[0]+1;
    }
    b=0;
    if(h[0][1]+h[1][1]==c && (h[1][1]%2==1 || op[1].size()>0))b=1;
    dp[1][0^a[x]][x]=b;
    cost[1][0^a[x]][x]=oo;
    if(b==1){
        if(h[1][0]%2==1)cost[1][0^a[x]][x]=sp[0]+1;
        else            cost[1][0^a[x]][x]=si[0]+1;
    }
    //cout<<x<<" "<<y<<"->"<<dp[0][0][x]<<" "<<dp[1][0][x]<<" "<<dp[0][0][x]<<" "<<dp[1][0][x]<<"\n";
return max(dp[0][0][x],dp[1][0][x]);
}
int main(){
    fast_in
    cin>>n;ll a1,a2;
    for(int i=1;i<n;i++){
        cin>>a1>>a2;
        v[a1].push_back(a2);
        v[a2].push_back(a1);
    }
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    if(dfs(1,1)==0){
        cout<<"impossible\n";
    }
    else{
        cout<<min(cost[0][0][1],cost[1][0][1]);
    }
return 0;
}

Compilation message (stderr)

xanadu.cpp: In function 'll dfs(ll, ll)':
xanadu.cpp:37:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for(int j=1;j+1<op[i].size();j++){
      |                     ~~~^~~~~~~~~~~~~

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