Submission #468487

#	Time	Username	Problem	Language	Result	Execution time	Memory
468487		kderylo	The Xana coup (BOI21_xanadu)	C++17	100 / 100	124 ms	27072 KiB

xanadu

#include <iostream>
#include <vector>
#include <set>
using namespace std;
const int stala=1e5+10;
vector<int>wektor[stala];
set<int>s;
int pom[stala];
int dp[stala][2][2][2]; //poprzednie obecny ojciec
bool o[stala][2][2][2];
int wierzcholek,war,war2,suma,ile_zapalonych;
void dfs(int k,int p)
{
    for(int i=0; i<(int)wektor[k].size(); i++)
    {
        if(wektor[k][i]!=p)
        {
            dfs(wektor[k][i],k);
        }
    }
    for(int i=0; i<=1; i++)
    {
        for(int j=0; j<=1; j++)
        {
            for(int z=0; z<=1; z++)
            {
                suma=0;
                ile_zapalonych=0;
                bool xyz=true;
                if((i+j+z)%2!=pom[k])
                {
                    continue;
                }
                for(int a=0; a<(int)wektor[k].size(); a++)
                {
                    war=1e9;
                    war2=1e9;
                    if(wektor[k][a]!=p)
                    {
                        wierzcholek=wektor[k][a];
                        if(o[wierzcholek][0][0][j]==1)
                        {
                            war=min(war,dp[wierzcholek][0][0][j]);
                        }
                        if(o[wierzcholek][1][0][j]==1)
                        {
                            war=min(war,dp[wierzcholek][1][0][j]);
                        }
                        if(o[wierzcholek][0][1][j]==1)
                        {
                            war2=min(war2,dp[wierzcholek][0][1][j]);
                        }
                        if(o[wierzcholek][1][1][j]==1)
                        {
                            war2=min(war2,dp[wierzcholek][1][1][j]);
                        }
                        if(war==1e9&&war2==1e9)
                        {
                            xyz=false;
                        }
                        else if(war!=1e9&&war2==1e9)
                        {
                            suma+=war;
                        }
                        else if(war==1e9&&war2!=1e9)
                        {
                            ile_zapalonych++;
                            suma+=war2;
                        }
                        else
                        {
                            suma+=war;
                            s.insert(war2-war);
                        }
                    }
                }
                if(xyz==false)
                {
                    s.clear();
                    continue;
                }
                xyz=false;
                dp[k][i][j][z]=1e9;
                if(ile_zapalonych%2==i)
                {
                    xyz=true;
                    dp[k][i][j][z]=min(dp[k][i][j][z],suma);
                }
                while(!s.empty())
                {
                    suma+=*(s.begin());
                    s.erase(s.begin());
                    ile_zapalonych++;
                    if(ile_zapalonych%2==i)
                    {
                        xyz=true;
                        dp[k][i][j][z]=min(dp[k][i][j][z],suma);
                    }
                }
                if(xyz==true)
                {
                    o[k][i][j][z]=1;
                    dp[k][i][j][z]+=j;
                }
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ile;
    cin>>ile;
    for(int i=1; i<=ile-1; i++)
    {
        int a,b;
        cin>>a>>b;
        wektor[a].push_back(b);
        wektor[b].push_back(a);
    }
    for(int i=1; i<=ile; i++)
    {
        cin>>pom[i];
    }
    dfs(1,0);
    int res=1e9;
    for(int i=0;i<=1;i++)
    {
        for(int j=0;j<=1;j++)
        {
            if(o[1][i][j][0]==1)
            {
                res=min(res,dp[1][i][j][0]);
            }
        }
    }
    if(res==1e9)
    {
        cout<<"impossible";
    }
    else
    {
        cout<<res;
    }

    return 0;
}

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