Submission #777701

#	Time	Username	Problem	Language	Result	Execution time	Memory
777701		borisAngelov	Džumbus (COCI19_dzumbus)	C++17	110 / 110	61 ms	30224 KiB

dzumbus

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1005;
const long long inf = 1e18;

int n, m;

bool visited[maxn];
int subtree_size[maxn];

long long d[maxn];

vector<int> g[maxn];

vector<long long> dp[maxn][3];

void dfs_trav(int node)
{
    visited[node] = true;

    for (auto next_node : g[node])
    {
        if (visited[next_node] == false)
        {
            dfs_trav(next_node);
        }
    }
}

void dfs_subtree(int node, int par)
{
    subtree_size[node] = 1;

    for (auto next_node : g[node])
    {
        if (next_node != par)
        {
            dfs_subtree(next_node, node);
            subtree_size[next_node] += subtree_size[node];
        }
    }
}

void to_combine(int node, int child)
{
    vector<long long> combine[3];

    combine[0].resize(dp[node][0].size() + dp[child][0].size() + 2, inf);
    combine[1].resize(dp[node][0].size() + dp[child][0].size() + 2, inf);
    combine[2].resize(dp[node][0].size() + dp[child][0].size() + 2, inf);

    for (int i = 0; i < dp[node][0].size(); ++i)
    {
        for (int j = 0; j < dp[child][0].size(); ++j)
        {
            combine[0][i + j] = min(combine[0][i + j], dp[node][0][i] + dp[child][0][j]);
        }
    }

    for (int i = 0; i < dp[node][0].size(); ++i)
    {
        for (int j = 0; j < dp[child][1].size(); ++j)
        {
            combine[0][i + j] = min(combine[0][i + j], dp[node][0][i] + dp[child][1][j]);
        }
    }

    for (int i = 0; i < dp[node][0].size(); ++i)
    {
        for (int j = 0; j < dp[child][2].size(); ++j)
        {
            combine[0][i + j] = min(combine[0][i + j], dp[node][0][i] + dp[child][2][j]);
        }
    }

    for (int i = 0; i < min(combine[0].size(), combine[1].size()); ++i)
    {
        combine[1][i] = min(combine[1][i], combine[0][i] + d[node]);
    }

    for (int i = 0; i < dp[node][0].size(); ++i)
    {
        for (int j = 0; j < dp[child][0].size(); ++j)
        {
            if (i + j + 2 < combine[2].size())
            {
                combine[2][i + j + 2] = min(combine[2][i + j + 2], dp[node][1][i] + dp[child][1][j]);
            }

            if (i + j + 1 < combine[2].size())
            {
                combine[2][i + j + 1] = min(combine[2][i + j + 1], dp[node][1][i] + dp[child][2][j]);
            }


            combine[2][i + j] = min(combine[2][i + j], dp[node][2][i] + dp[child][2][j]);

            if (i + j + 1 < combine[2].size())
            {
                combine[2][i + j + 1] = min(combine[2][i + j + 1], dp[node][2][i] + dp[child][1][j]);
            }

            combine[2][i + j] = min(combine[2][i + j], dp[node][2][i] + dp[child][0][j]);
        }
    }

    dp[node][0] = combine[0];
    dp[node][1] = combine[1];
    dp[node][2] = combine[2];
}

void dfs(int node)
{
    dp[node][0] = {0};
    dp[node][1] = {d[node]};
    dp[node][2] = {inf};

    visited[node] = true;

    for (auto next_node : g[node])
    {
        if (visited[next_node] == false)
        {
            dfs(next_node);
            to_combine(node, next_node);
        }
    }
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
    {
        cin >> d[i];
    }

    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        cin >> x >> y;

        g[x].push_back(y);
        g[y].push_back(x);
    }

    int root = 0;

    for (int i = 1; i <= n; ++i)
    {
        if (visited[i] == false)
        {
            dfs_trav(i);
            g[0].push_back(i);
        }
    }

    dfs_subtree(0, -1);

    for (int i = 1; i <= n; ++i)
    {
        visited[i] = false;
    }

    dfs(0);

    int q;
    cin >> q;

    for (int i = 1; i <= q; ++i)
    {
        long long x;
        cin >> x;

        int l = 2;
        int r = n;

        while (l <= r)
        {
            int mid = (l + r) / 2;

            if (dp[root][0][mid] <= x)
            {
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }

        if (r < 2)
        {
            cout << 0 << "\n";
        }
        else
        {
            cout << r << "\n";
        }
    }

    return 0;
}

Compilation message (stderr)

dzumbus.cpp: In function 'void to_combine(int, int)':
dzumbus.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i = 0; i < dp[node][0].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int j = 0; j < dp[child][0].size(); ++j)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (int i = 0; i < dp[node][0].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:64:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for (int j = 0; j < dp[child][1].size(); ++j)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:70:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (int i = 0; i < dp[node][0].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:72:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for (int j = 0; j < dp[child][2].size(); ++j)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:78:23: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   78 |     for (int i = 0; i < min(combine[0].size(), combine[1].size()); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:83:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for (int i = 0; i < dp[node][0].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:85:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for (int j = 0; j < dp[child][0].size(); ++j)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:87:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |             if (i + j + 2 < combine[2].size())
      |                 ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
dzumbus.cpp:92:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |             if (i + j + 1 < combine[2].size())
      |                 ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
dzumbus.cpp:100:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             if (i + j + 1 < combine[2].size())
      |                 ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30