Submission #575447

#	Time	Username	Problem	Language	Result	Execution time	Memory
575447		timreizin	The Xana coup (BOI21_xanadu)	C++17	100 / 100	120 ms	27792 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});
    //first bit - he, second - father
    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);
            }
        }
        //we don't do operation
        //then parity of number of ones
        //let sum = dp[u][0], d_i = dp[u][2] - dp[u][0]
        //depending on parity we add to one or other mask
        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];
                }
            }
        }
        //we do operation
        //then parity of number of ones
        //let sum = dp[u][1], d_i = dp[u][3] - dp[u][1]
        //depending on parity we add to one or other mask
        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;
}
/*
5
1 2
1 3
2 4
2 5
0 1 0 1 1
*/

/*
2|1 7|0
3|1 17|1
9|1 16|0
15|1 8|0
6|0 13|0
7|0 10|0
12|0 17|1
12|0 4|0
1|0 11|0
7|0 15|1
3|1 14|1
11|0 17|1
8|0 17|1
1|0 5|1
13|0 7|0
8|0 16|0
*/

Compilation message (stderr)

xanadu.cpp: In lambda function:
xanadu.cpp:74:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             for (int i = 0; i <= deltas.size(); ++i)
      |                             ~~^~~~~~~~~~~~~~~~
xanadu.cpp:114:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             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:125:18:   required from here
xanadu.cpp:74:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             for (int i = 0; i <= deltas.size(); ++i)
      |                             ~~^~~~~~~~~~~~~~~~
xanadu.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |                 if (i != deltas.size())
      |                     ~~^~~~~~~~~~~~~~~~
xanadu.cpp:114:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             for (int i = 0; i <= deltas.size(); ++i)
      |                             ~~^~~~~~~~~~~~~~~~
xanadu.cpp:117:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |                 if (i != deltas.size())
      |                     ~~^~~~~~~~~~~~~~~~

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