Submission #447226

#	Time	Username	Problem	Language	Result	Execution time	Memory
447226		prvocislo	The Xana coup (BOI21_xanadu)	C++17	100 / 100	114 ms	20032 KiB

xanadu

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

const int maxn = 1e5 + 5, inf = 1e9 + 5;
void upd(int &a, const int &b) { a = min(a, b); }
int dp[maxn][2][2], b[maxn];
vector<int> g[maxn];
void dfs(int u, int p = -1)
{
    int dp2[2][2];
    for (int i = 0; i < 2; i++) 
    {
        for (int j = 0; j < 2; j++) dp2[i][j] = inf;
        dp2[i][b[u]] = 0;
    }
    for (int v : g[u]) if (v != p)
    {
        dfs(v, u);
        int nw[2][2];
        for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) nw[i][j] = inf;
        for (int me = 0; me < 2; me++) for (int par = 0; par < 2; par++) if (dp[v][me][par] != inf)
        {
            for (int cur = 0; cur < 2; cur++)
            {
                upd(nw[me][cur ^ par], dp2[me][cur] + dp[v][me][par]);
            }
        }
        for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) dp2[i][j] = nw[i][j];
    }
    for (int stav = 0; stav < 2; stav++) for (int moj = 0; moj < 2; moj++)
    {
        upd(dp[u][moj^stav][stav], dp2[stav][moj] + stav);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n; cin >> n;
    for (int i = 0; i < n; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) dp[i][j][k] = inf;
    for (int i = 0, a, b; i < n-1; i++) cin >> a >> b, g[--a].push_back(--b), g[b].push_back(a);
    for (int i = 0; i < n; i++) cin >> b[i];
    dfs(0);
    int ans = min(dp[0][0][0], dp[0][0][1]);
    if (ans != inf) cout << ans << "\n";
    else cout << "impossible\n";
    return 0;
}

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