Submission #1134017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134017		heeheeheehaaw	The Xana coup (BOI21_xanadu)	C++20	100 / 100	87 ms	26440 KiB

xanadu

#include <bits/stdc++.h>

using namespace std;

int dp[100005][2][2];
int v[100005];
vector<int> adj[100005];
const int INF = 1e9;

void dfs(int nod, int parent)
{
    bool ok = false;
    for(auto it : adj[nod])
    {
        if(it != parent)
        {
            ok = true;
            dfs(it, nod);
        }
    }

    if(ok == false)
    {
        if(v[nod] == 1)
        {
            dp[nod][0][0] = INF;
            dp[nod][0][1] = 0;
            dp[nod][1][0] = 1;
            dp[nod][1][1] = INF;
        }
        else
        {
            dp[nod][0][0] = 0;
            dp[nod][0][1] = INF;
            dp[nod][1][0] = INF;
            dp[nod][1][1] = 1;
        }
    }
    else
    {
        dp[nod][0][0] = dp[nod][0][1] = dp[nod][1][0] = dp[nod][1][1] = INF;
        {
            int sum = 0, pr = v[nod];
            bool ok = true;
            priority_queue<int> pq;
            for(auto it : adj[nod])
            {
                if(it != parent)
                {
                    if(dp[it][0][0] != INF)
                    {
                        sum += dp[it][0][0];
                        if(dp[it][1][0] != INF)
                            pq.push(-(-dp[it][0][0] + dp[it][1][0]));
                    }
                    else
                    {
                        if(dp[it][1][0] != INF)
                        {
                            sum += dp[it][1][0];
                            pr = (pr + 1) % 2;
                        }
                        else
                        {
                            ok = false;
                        }
                    }
                }

            }

            dp[nod][0][pr] = sum;
            while(!pq.empty())
            {
                sum += -pq.top();
                pq.pop();
                pr = (pr + 1) % 2;
                dp[nod][0][pr] = min(dp[nod][0][pr], sum);
            }

            if(ok == false)
                dp[nod][0][0] = dp[nod][0][1] = INF;
        }

        {
            int sum = 0, pr = 1 - v[nod];
            bool ok = true;
            priority_queue<int> pq;
            for(auto it : adj[nod])
            {
                if(it != parent)
                {
                    if(dp[it][0][1] != INF)
                    {
                        sum += dp[it][0][1];
                        if(dp[it][1][1] != INF)
                            pq.push(-(-dp[it][0][1] + dp[it][1][1]));
                    }
                    else
                    {
                        if(dp[it][1][1] != INF)
                        {
                            sum += dp[it][1][1];
                            pr = (pr + 1) % 2;
                        }
                        else
                        {
                            ok = false;
                        }
                    }
                }

            }

            dp[nod][1][pr] = sum + 1;
            while(!pq.empty())
            {
                sum += -pq.top();
                pq.pop();
                pr = (pr + 1) % 2;
                dp[nod][1][pr] = min(dp[nod][1][pr], sum + 1);
            }

            if(ok == false)
                dp[nod][1][0] = dp[nod][1][1] = INF;
        }

    }
}

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

    for(int i = 1; i <= n; i++)
        cin>>v[i];

    dfs(1, 1);
    if(min(dp[1][1][0], dp[1][0][0]) != INF)
        cout<<min(dp[1][1][0], dp[1][0][0]);
    else
        cout<<"impossible";
    return 0;
}

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