Submission #575448

#	Time	Username	Problem	Language	Result	Execution time	Memory
575448		timreizin	The Xana coup (BOI21_xanadu)	C++17	100 / 100	115 ms	26564 KiB

xanadu

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>

using namespace std;

using ll = long long;

const ll INF = 1e8;

int main()
{
    int n;
    cin >> n;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i + 1 < n; ++i)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    vector<int> a(n);
    for (int &i : a) cin >> i;
    a.insert(a.begin(), 0);
    vector<array<ll, 4>> dp(n + 1, {INF, INF, INF, INF});
    auto dfs = [&adj, &a, &dp](auto self, int v, int p) -> void
    {
        if (adj[v].size() == 1 && p != 0)
        {
            dp[v][a[v]] = 0;
            dp[v][3 - a[v]] = 1;
            return;
        }
        for (int u : adj[v])
        {
            if (u != p)
            {
                self(self, u, v);
            }
        }
        vector<ll> deltas;
        ll sum = 0;
        int cnt = 0;
        for (int u : adj[v])
        {
            if (u != p)
            {
                if (dp[u][0] == INF && dp[u][2] == INF)
                {
                    sum = -1;
                    break;
                }
                if (dp[u][0] == INF)
                {
                    sum += dp[u][2];
                    ++cnt;
                    continue;
                }
                sum += dp[u][0];
                if (dp[u][2] != INF) deltas.push_back(dp[u][2] - dp[u][0]);
            }
        }
        if (sum != -1)
        {
            sort(deltas.begin(), deltas.end());
            cnt += a[v];
            for (int i = 0; i <= deltas.size(); ++i)
            {
                dp[v][cnt & 1] = min(dp[v][cnt & 1], sum);
                if (i != deltas.size())
                {
                    ++cnt;
                    sum += deltas[i];
                }
            }
        }
        deltas.clear();
        sum = 0;
        cnt = 1;
        for (int u : adj[v])
        {
            if (u != p)
            {
                if (dp[u][1] == INF && dp[u][3] == INF)
                {
                    sum = -1;
                    break;
                }
                if (dp[u][1] == INF)
                {
                    sum += dp[u][3];
                    ++cnt;
                    continue;
                }
                sum += dp[u][1];
                if (dp[u][3] != INF) deltas.push_back(dp[u][3] - dp[u][1]);
            }
        }
        if (sum != -1)
        {
            sort(deltas.begin(), deltas.end());
            cnt += a[v];
            for (int i = 0; i <= deltas.size(); ++i)
            {
                dp[v][2 + (cnt & 1)] = min(dp[v][2 + (cnt & 1)], sum + 1);
                if (i != deltas.size())
                {
                    ++cnt;
                    sum += deltas[i];
                }
            }
        }
    };
    dfs(dfs, 1, 0);
    if (min(dp[1][0], dp[1][2]) == INF) cout << "impossible";
    else cout << min(dp[1][0], dp[1][2]);
    return 0;
}

Compilation message (stderr)

xanadu.cpp: In lambda function:
xanadu.cpp:69:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             for (int i = 0; i <= deltas.size(); ++i)
      |                             ~~^~~~~~~~~~~~~~~~
xanadu.cpp:105:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             for (int i = 0; i <= deltas.size(); ++i)
      |                             ~~^~~~~~~~~~~~~~~~
xanadu.cpp: In instantiation of 'main()::<lambda(auto:1, int, int)> [with auto:1 = main()::<lambda(auto:1, int, int)>]':
xanadu.cpp:116:18:   required from here
xanadu.cpp:69:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             for (int i = 0; i <= deltas.size(); ++i)
      |                             ~~^~~~~~~~~~~~~~~~
xanadu.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |                 if (i != deltas.size())
      |                     ~~^~~~~~~~~~~~~~~~
xanadu.cpp:105:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             for (int i = 0; i <= deltas.size(); ++i)
      |                             ~~^~~~~~~~~~~~~~~~
xanadu.cpp:108:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |                 if (i != deltas.size())
      |                     ~~^~~~~~~~~~~~~~~~

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