Submission #720895

#	Time	Username	Problem	Language	Result	Execution time	Memory
720895		Johann	The Xana coup (BOI21_xanadu)	C++14	10 / 100	69 ms	22400 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;

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?]
    dp[0][L[0]][0] = 0;
    dp[0][L[0] ^ 1][1] = 1;

    for (int i = 1; i < N; ++i)
        for (int schalten = 0; schalten < 2; ++schalten)
        {
            int res = L[i] ^ schalten;
            if (dp[i - 1][schalten][0] != INT_MAX)
                dp[i][res][schalten] = min(dp[i][res][schalten], dp[i - 1][schalten][0] + schalten);
            if (dp[i - 1][schalten][1] != INT_MAX)
                dp[i][res ^ 1][schalten] = min(dp[i][res ^ 1][schalten], dp[i - 1][schalten][1] + schalten);
        }

    int ans = min(dp[N - 1][0][0], dp[N - 1][0][1]);
    if (ans != INT_MAX)
        cout << ans << "\n";
    else
        cout << "impossible\n";

    return 0;
}

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