제출 #720899

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
720899		Johann	The Xana coup (BOI21_xanadu)	C++14	100 / 100	146 ms	39544 KiB

xanadu

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

#define ll long long
#define pii pair<int, int>
#define vb vector<bool>
#define vi vector<int>
#define vpii vector<pii>
#define vvb vector<vb>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vvpii vector<vpii>
#define sz(x) (int)(x).size()

int N;
vi L;
vvi adj;
vvvi dp;

void dfs(int v, int p)
{

    for (int u : adj[v])
        if (u != p)
            dfs(u, v);

    for (int schalten = 0; schalten < 2; ++schalten)
    {
        vvi res(1, vi(2, INT_MAX));
        res[0][L[v] ^ schalten] = schalten;
        int i = 0;
        for (int u : adj[v])
        {
            if (u == p)
                continue;
            res.push_back(vi(2, INT_MAX));
            ++i;
            if (dp[u][schalten][0] != INT_MAX)
            {
                if (res[i - 1][0] != INT_MAX)
                    res[i][0] = min(res[i][0], res[i - 1][0] + dp[u][schalten][0]);
                if (res[i - 1][1] != INT_MAX)
                    res[i][1] = min(res[i][1], res[i - 1][1] + dp[u][schalten][0]);
            }
            if (dp[u][schalten][1] != INT_MAX)
            {
                if (res[i - 1][1] != INT_MAX)
                    res[i][0] = min(res[i][0], res[i - 1][1] + dp[u][schalten][1]);
                if (res[i - 1][0] != INT_MAX)
                    res[i][1] = min(res[i][1], res[i - 1][0] + dp[u][schalten][1]);
            }
        }
        dp[v][0][schalten] = res.back()[0];
        dp[v][1][schalten] = res.back()[1];
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    adj.resize(N);
    for (int i = 0, a, b; i < N - 1; ++i)
    {
        cin >> a >> b;
        --a, --b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    L.resize(N);
    for (int i = 0; i < N; ++i)
        cin >> L[i];

    dp.assign(N, vvi(2, vi(2, INT_MAX))); // [node][res][wurde geschaltet?]

    dfs(0, 0);

    int ans = min(dp[0][0][0], dp[0][0][1]);
    if (ans != INT_MAX)
        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