Submission #1243858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243858		chikien2009	The Xana coup (BOI21_xanadu)	C++20	100 / 100	32 ms	16964 KiB

xanadu

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, a, b, f[100000][2][2], res;
bool state[100000];
vector<int> g[100000];

inline void DFS(int node, int par)
{
    int c[2][2] = {{0, 0}, {(int)1e9, (int)1e9}}, d[2][2];
    for (auto &i : g[node])
    {
        if (i != par)
        {
            DFS(i, node);
            for (int j = 0; j < 2; ++j)
            {
                for (int k = 0; k < 2; ++k)
                {
                    d[j][k] = min(c[j][k] + f[i][0][k], c[1 - j][k] + f[i][1][k]);
                }
            }
            for (int j = 0; j < 2; ++j)
            {
                for (int k = 0; k < 2; ++k)
                {
                    c[j][k] = min((int)1e9, d[j][k]);
                }
            }
        }
    }
    f[node][0][0] = c[state[node]][0];
    f[node][0][1] = c[1 - state[node]][0];
    f[node][1][0] = min((int)1e9, c[1 - state[node]][1] + 1);
    f[node][1][1] = min((int)1e9, c[state[node]][1] + 1);
}

int main()
{
    setup();

    cin >> n;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> a >> b;
        g[a - 1].push_back(b - 1);
        g[b - 1].push_back(a - 1);
    }
    for (int i = 0; i < n; ++i)
    {
        cin >> state[i];
    }
    DFS(0, 0);
    res = min(f[0][0][0], f[0][1][0]);
    if (res > 1e6)
    {
        cout << "impossible";
        return 0;
    }
    cout << res;
    return 0;
}

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