Submission #1034559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034559		Marco_Escandon	The Xana coup (BOI21_xanadu)	C++11	100 / 100	76 ms	29064 KiB

xanadu

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define x first
#define y second
ll cad[100005];
vector<ll> G[100005];
vector<vector<pair<ll,ll>>> cache;
pair<ll,ll> sol(ll node, ll padre, ll v)
{
    if(cache[node][v].x!=-1) return cache[node][v];
    pair<ll,ll> hoff={0,0}, hon={0,0};
    ll moff=1e9, mon=1e9;
    ll pl=false;
    for(auto i:G[node])
    {
        if(i==padre) continue;
        pl=true;
        pair<ll,ll> temp=sol(i,node, 0);
        hoff.x+=min(temp.x,temp.y);
        hoff.y+=(temp.y<temp.x);
        moff=min(moff,max(temp.x,temp.y)-min(temp.x,temp.y));

        temp=sol(i,node, 1);
        hon.x+=min(temp.x,temp.y);
        hon.y+=(temp.y<temp.x);
        mon=min(mon,max(temp.x,temp.y)-min(temp.x,temp.y));
    }
    ll sol1=1e9, sol2=1e9;
    if(cad[node]==v)
    {
        if(hoff.y%2!=0) hoff.x+=moff;
        sol1=hoff.x;

        if(hon.y%2!=1) hon.x+=mon;
        sol2=hon.x+1;
    }
    else
    {
        if(hoff.y%2!=1) hoff.x+=moff;
        sol1=hoff.x;

        if(hon.y%2!=0) hon.x+=mon;
        sol2=hon.x+1;
    }
    //cerr<<node<<v<<" "<<sol1<<" "<<sol2<<"\n";
    return cache[node][v]={sol1,sol2};
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    ll n;
    cin>>n;
    cache.assign(n+4,vector<pair<ll,ll>>(3,{-1,0}));
    for(int i=0; i<n-1; i++)
    {
        ll a,b;
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for(int i=1; i<=n; i++)
    {
        cin>>cad[i];
    }
    ll t1=min(sol(1,0,0).x,sol(1,0,0).y);
    if(t1>=1e9)
        cout<<"impossible";
    else 
        cout<<t1;
    return 0;
}

Compilation message (stderr)

xanadu.cpp: In function 'std::pair<long long int, long long int> sol(ll, ll, ll)':
xanadu.cpp:14:8: warning: variable 'pl' set but not used [-Wunused-but-set-variable]
   14 |     ll pl=false;
      |        ^~

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