Submission #674387

#	Time	Username	Problem	Language	Result	Execution time	Memory
674387		danikoynov	Džumbus (COCI19_dzumbus)	C++14	110 / 110	65 ms	30180 KiB

dzumbus

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1010;
const ll inf = 1e17;
int n, m, used[maxn], sub[maxn];
ll d[maxn];
vector < int > g[maxn];
vector < ll > dp[maxn][3];

void to_process(int v, int u)
{
    vector < ll > combine[3];
    ///cout << v << " : " << dp[v][0].size() << " " << dp[u][0].size() << endl;
    combine[0].resize(dp[v][0].size() + dp[u][0].size() + 2, inf);
    combine[1].resize(dp[v][0].size() + dp[u][0].size() + 2, inf);
    combine[2].resize(dp[v][0].size() + dp[u][0].size() + 2, inf);

    for (int i = 0; i < dp[v][0].size(); i ++)
        for (int j = 0; j < dp[u][0].size(); j ++)
            combine[0][i + j] = min(combine[0][i + j], dp[v][0][i] + dp[u][0][j]);
    for (int i = 0; i < dp[v][0].size(); i ++)
        for (int j = 0; j < dp[u][1].size(); j ++)
            combine[0][i + j] = min(combine[0][i + j], dp[v][0][i] + dp[u][1][j]);
    for (int i = 0; i < dp[v][0].size(); i ++)
        for (int j = 0; j < dp[u][2].size(); j ++)
            combine[0][i + j] = min(combine[0][i + j], dp[v][0][i] + dp[u][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[v]);


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

            combine[2][i + j] = min(combine[2][i + j], dp[v][2][i] + dp[u][2][j]);
            //if (v == 1)
            // cout << i << " "  << j << " " << v << " " << u << " " << dp[v][2][i] << " " << dp[u][0][j] << endl;
            if (i + j + 1 < combine[2].size())
                combine[2][i + j + 1] = min(combine[2][i + j + 1], dp[v][2][i] + dp[u][1][j]);
            combine[2][i + j] = min(combine[2][i + j], dp[v][2][i] + dp[u][0][j]);
        }
    //if (v == 1)
    // cout << combine[2][5] << " ::: " << combine[2][6] <<  endl;

    dp[v][0] = combine[0];
    dp[v][1] = combine[1];
    dp[v][2] = combine[2];

}
void calc_sub(int v, int par)
{
    sub[v] = 1;

    for (int u : g[v])
    {
        if (u != par)
        {
            calc_sub(u, v);
            sub[v] += sub[u];
        }
    }
}
void dfs(int v)
{
    //cout << "here " << v << endl;
    dp[v][0] = {0};
    dp[v][1] = {d[v]};
    dp[v][2] = {inf};
    used[v] = 1;

    for (int u : g[v])
    {
        if (used[u])
            continue;
        dfs(u);
        to_process(v, u);
    }
}

void trav(int v)
{
    used[v] = 1;
    for (int u : g[v])
    {
        if (!used[u])
            trav(u);
    }
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        cin >> d[i];
    for (int i = 1; i <= m; i ++)
    {
        int v, u;
        cin >> v >> u;
        g[v].push_back(u);
        g[u].push_back(v);
    }

    vector < int > roots;
    int root = 0;
    for (int i = 1; i <= n; i ++)
    {
        if (!used[i])
        {
            trav(i);
            g[root].push_back(i);
        }
    }
    calc_sub(0, -1);

    memset(used, 0, sizeof(used));
    int ver = 8;
    ///cout << "dfs " << ver << endl;
    dfs(0);

    /**for (int type = 0; type < 3; type ++, cout << endl)
    for (int j = 0; j < dp[ver][type].size(); j ++)
       cout << dp[ver][type][j] << " ";*/


    int q;
    cin >> q;
    for (int t = 0; t < q; t ++)
    {
        ll x;
        cin >> x;
        ll lf = 2, rf = n;
        while(lf <= rf)
        {
            int mf = (lf + rf) / 2;
            if (dp[root][0][mf] <= x)
                lf = mf + 1;
            else
                rf = mf - 1;
        }
        if (rf < 2)
            cout << 0 << endl;
        else
            cout << rf << endl;
    }
}

int main()
{
    speed();
    solve();
    return 0;
}

Compilation message (stderr)

dzumbus.cpp: In function 'void to_process(int, int)':
dzumbus.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i = 0; i < dp[v][0].size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:38:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for (int j = 0; j < dp[u][0].size(); j ++)
      |                         ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i = 0; i < dp[v][0].size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int j = 0; j < dp[u][1].size(); j ++)
      |                         ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < dp[v][0].size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for (int j = 0; j < dp[u][2].size(); j ++)
      |                         ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   47 |     for (int i = 0; i < min(combine[0].size(), combine[1].size()); i ++)
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:51:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int i = 0; i < dp[v][0].size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:52:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for (int j = 0; j < dp[u][0].size(); j ++)
      |                         ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:54:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             if (i + j + 2 < combine[2].size())
      |                 ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
dzumbus.cpp:58:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             if (i + j + 1 < combine[2].size())
      |                 ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
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 |             if (i + j + 1 < combine[2].size())
      |                 ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
dzumbus.cpp: In function 'void solve()':
dzumbus.cpp:142:9: warning: unused variable 'ver' [-Wunused-variable]
  142 |     int ver = 8;
      |         ^~~

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