Submission #884921

#	Time	Username	Problem	Language	Result	Execution time	Memory
884921		maxFedorchuk	The Xana coup (BOI21_xanadu)	C++17	100 / 100	51 ms	15852 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;

const long long MX=1e5+10;

vector < long long > mas[MX];
long long st[MX];

long long mn[MX][2][2];

long long n;

void DFS(long long zar,long long mun)
{
    for(auto u:mas[zar])
    {
        if(u!=mun)
        {
            DFS(u,zar);
        }
    }

    if(st[zar])
    {
        mn[zar][0][1]=0;
        mn[zar][1][1]=n+1;

        mn[zar][0][0]=n+1;
        mn[zar][1][0]=1;
    }
    else
    {
        mn[zar][0][1]=n+1;
        mn[zar][1][1]=1;

        mn[zar][0][0]=0;
        mn[zar][1][0]=n+1;
    }

    for(auto u:mas[zar])
    {
        if(u==mun)
        {
            continue;
        }

        long long zn00=mn[zar][0][0];
        long long zn01=mn[zar][0][1];
        long long zn10=mn[zar][1][0];
        long long zn11=mn[zar][1][1];

        mn[zar][0][0]=min({zn00+mn[u][0][0],zn01+mn[u][1][0],n+1});
        mn[zar][0][1]=min({zn00+mn[u][1][0],zn01+mn[u][0][0],n+1});

        mn[zar][1][0]=min({zn10+mn[u][0][1],zn11+mn[u][1][1],n+1});
        mn[zar][1][1]=min({zn11+mn[u][0][1],zn10+mn[u][1][1],n+1});
    }

    return;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin>>n;

    long long a,b;
    for(long long i=1;i<n;i++)
    {
        cin>>a>>b;
        mas[a].push_back(b);
        mas[b].push_back(a);
    }

    for(long long i=1;i<=n;i++)
    {
        cin>>st[i];
    }

    DFS(1,0);

    if(min(mn[1][0][0],mn[1][1][0])>n)
    {
        cout<<"impossible\n";
    }
    else
    {
        cout<<min(mn[1][0][0],mn[1][1][0])<<"\n";
    }

    return 0;
}

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