Submission #725766

#	Time	Username	Problem	Language	Result	Execution time	Memory
725766		LittleCube	The Xana coup (BOI21_xanadu)	C++14	100 / 100	94 ms	22768 KiB

xanadu

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

// dp[op][cur]
// op = 1: all subtree cur == 0
// op = 0: all subtree cur == 1
ll N, p[100005], a[100005], dp[100005][2][2];
vector<int> E[100005];

void dfs(int u)
{
    // dp[u][0][0] = dp[u][0][1] = dp[u][1][0] = dp[u][1][1] = N + 1;
    ll dcur = a[u], ncur = a[u], d = N + 1, n = N + 1, dcost = 0, ncost = 0;
    for (int v : E[u])
        if (p[u] != v)
        {
            //cerr << u << " -> " << v << '\n';
            p[v] = u;
            dfs(v);

            dcur ^= (dp[v][0][1] < dp[v][1][1] ? 0 : 1);
            dcost += min(dp[v][0][1], dp[v][1][1]);
            d = min(d, abs(dp[v][0][1] - dp[v][1][1]));

            ncur ^= (dp[v][0][0] < dp[v][1][0] ? 0 : 1);
            ncost += min(dp[v][0][0], dp[v][1][0]);
            n = min(n, abs(dp[v][0][0] - dp[v][1][0]));
        }
    dp[u][1][dcur ^ 1] = dcost + 1;
    dp[u][1][dcur] = dcost + d + 1;
    dp[u][0][ncur] = ncost;
    dp[u][0][ncur ^ 1] = ncost + n;
    //cerr << u << ": " << dp[u][0][0] << ' ' << dp[u][0][1] << ' ' << dp[u][1][0] << ' ' << dp[u][1][1] << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> N;
    for (int i = 1; i < N; i++)
    {
        int u, v;
        cin >> u >> v;
        E[u].emplace_back(v);
        E[v].emplace_back(u);
    }
    for (int i = 1; i <= N; i++)
        cin >> a[i];
    dfs(1);
    int ans = min(dp[1][0][0], dp[1][1][0]);
    if (ans > N)
        cout << "impossible\n";
    else
        cout << ans << '\n';
}

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