Submission #1043183

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

xanadu

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vll vector<ll>
#define MAX 500005

const ll oo=1e18;
ll n,a[MAX],a1,a2,dp[5][5][MAX],co[5][5][MAX];
vll v[MAX];
void dfs(ll x,ll y){
    ll h[2]={0,0},sp[2]={0,0},si[2]={oo,oo};
    vll v1[2]={{},{}};ll p[2]={0,0};
    for(auto w : v[x]){
        if(w==y)continue;
        dfs(w,x);
        for(int i=0;i<2;i++){
            if(co[0][i][w]!=oo){
                sp[i]+=co[0][i][w];
                if(co[1][i][w]!=oo){
                    v1[i].push_back(co[1][i][w]-co[0][i][w]);
                }
                continue;
            }
            p[i]++;
            if(co[1][i][w]!=oo)sp[i]+=co[1][i][w];
            else h[i]=1;
        }
    }
    for(int i=0;i<2;i++){
        if(h[i]==1)continue;
        sort(v1[i].begin(),v1[i].end());
        ll b=sp[i];
        for(int j=0;j<v1[i].size();j++){
            if(j>0)v1[i][j]+=v1[i][j-1];
            if(j%2==1)sp[i]=min(sp[i],b+v1[i][j]);
            if(j%2==0)si[i]=min(si[i],b+v1[i][j]);
        }
    }
    co[0][0^a[x]][x]=oo;
    if(h[0]==0){
        if(p[0]%2==0)co[0][0^a[x]][x]=sp[0];
        else         co[0][0^a[x]][x]=si[0];
    }
    co[1][1^a[x]][x]=oo;
    if(h[1]==0){
        if(p[1]%2==0)co[1][1^a[x]][x]=min(sp[1]+1LL,oo);
        else         co[1][1^a[x]][x]=min(si[1]+1LL,oo);
    }
    co[0][1^a[x]][x]=oo;
    if(h[0]==0){
        if(p[0]%2==1)co[0][1^a[x]][x]=sp[0];
        else         co[0][1^a[x]][x]=si[0];
    }
    co[1][0^a[x]][x]=oo;
    if(h[1]==0){
        if(p[1]%2==1)co[1][0^a[x]][x]=min(sp[1]+1LL,oo);
        else         co[1][0^a[x]][x]=min(si[1]+1LL,oo);
    }
   // cerr<<co[0][0][x]<<" "<<co[1][0][x]<<"\n";
}
int main(){
    cin>>n;
    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];
    }
    dfs(1,1);
    if(min(co[0][0][1],co[1][0][1])==oo)cout<<"impossible\n";
    else                                cout<<min(co[0][0][1],co[1][0][1])<<"\n";


return 0;
}

Compilation message (stderr)

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

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