Submission #674378

#	Time	Username	Problem	Language	Result	Execution time	Memory
674378		danikoynov	Džumbus (COCI19_dzumbus)	C++14	30 / 110	1069 ms	15924 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 = 1e18;
int n, m, used[maxn];
ll d[maxn];
vector < int > g[maxn];
vector < ll > dp[maxn][3];

void to_process(int v, int u)
{
    vector < ll > combine[3];
    combine[0] = dp[v][0];
    combine[1] = dp[v][1];
    combine[2] = dp[v][2];

    for (int i = 0; i <= n; i ++)
        for (int j = 0; j <= n - i; j ++)
    {

        combine[0][i + j] = min(combine[0][i + j], dp[v][0][i] + min(dp[u][0][j], min(dp[u][1][j], dp[u][2][j])));
    }

    for (int i = 0; i <= n; i ++)
        combine[1][i] = min(combine[1][i], combine[0][i] + d[v]);


       for (int i = 0; i <= n; i ++)
        for (int j = 0; j <= n - i; j ++)
    {

        combine[2][i + j + 2] = min(combine[2][i + j + 2], dp[v][1][i] + dp[u][1][j]);
        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;
        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 dfs(int v)
{
    ///cout << "here " << v << endl;
    dp[v][0].resize(n + 3, inf);
    dp[v][1].resize(n + 3, inf);
    dp[v][2].resize(n + 3, inf);
    dp[v][0][0] = 0;
    dp[v][1][0] = d[v];
    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);
        }
    }
    memset(used, 0, sizeof(used));
    int ver = 0;
    ///cout << "dfs " << ver << endl;
    dfs(0);
    ///cout << dp[1][2][3] << endl;

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

    //exit(0);
    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 solve()':
dzumbus.cpp:120:9: warning: unused variable 'ver' [-Wunused-variable]
  120 |     int ver = 0;
      |         ^~~

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