Submission #1034410

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034410		Marco_Escandon	The Xana coup (BOI21_xanadu)	C++11	0 / 100	55 ms	27472 KiB

xanadu

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const string ny[2] = {"No", "Yes"};
#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};
    for(auto i:G[node])
    {
        if(i==padre) continue;
        pair<ll,ll> temp=sol(i,node, 0);
        hoff.x+=temp.x;
        hoff.y+=temp.y;

        temp=sol(i,node, 1);
        hon.x+=temp.x;
        hon.y+=temp.y;
    }
    pair<ll,ll> sol1={1e9,0}, sol2={1e9,0};
    if(cad[node]==v)
    {
        if(hoff.y%2==0)
        {
            sol1.x=hoff.x;
            sol1.y=0;
        }
        if(hon.y%2==1)
        {
            sol2.x=hon.x+1;
            sol2.y=1;
        }
    }
    else
    {
        if(hoff.y%2==1)
        {
            sol1.x=hoff.x;
            sol1.y=0;
        }
        if(hon.y%2==0)
        {
            sol2.x=hon.x+1;
            sol2.y=1;
        }
    }
    return cache[node][v]=min(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];
    }
    if(sol(1,0,0).x==1e9)
        cout<<"impossible";
    else 
        cout<<sol(1,0,0).x;
    return 0;
}

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