Submission #912722

#	Time	Username	Problem	Language	Result	Execution time	Memory
912722		CyberCow	Džumbus (COCI19_dzumbus)	C++17	110 / 110	41 ms	27156 KiB

dzumbus

#include <random>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <chrono>
#define fr first
#define sc second
#define ad push_back
using namespace std;
using ll = long long;
mt19937 rnd(348502);

const ll N = 1010;

ll dp[N][N][3];
ll dpp[N][3];
ll d[N];
vector<int> v[N];
int color[N], ma[N], n;

void Dfs(int g, int p)
{
    color[g] = 1;
    for (auto to : v[g])
    {
        if (to != p)
        {
            if (g != n + 1)
                Dfs(to, g);
        }
    }
    ma[g] = 1;
    dp[g][0][1] = d[g];
    dp[g][0][0] = 0;
    for (auto to : v[g])
    {
        if (to != p)
        {
            for (int i = 0; i <= ma[g] + ma[to] + 2; i++)
            {
                dpp[i][0] = 1e15;
                dpp[i][1] = 1e15;
                dpp[i][2] = 1e15;
            }
            for (int i = 0; i <= ma[g]; i++)
            {
                for (int j = 0; j <= ma[to]; j++)
                {
                    dpp[i + j + 1][2] = min(dpp[i + j + 1][2], dp[g][i][2] + dp[to][j][1]);
                    dpp[i + j + 1][2] = min(dpp[i + j + 1][2], dp[g][i][1] + dp[to][j][2]);
                    dpp[i + j + 2][2] = min(dpp[i + j + 2][2], dp[g][i][1] + dp[to][j][1]);
                    dpp[i + j][2] = min(dpp[i + j][2], dp[g][i][2] + dp[to][j][2]);
                    dpp[i + j][2] = min(dpp[i + j][2], dp[g][i][2] + dp[to][j][0]);

                    dpp[i + j][1] = min(dpp[i + j][1], dp[g][i][1] + dp[to][j][0]);

                    dpp[i + j][0] = min(dpp[i + j][0], dp[g][i][0] + dp[to][j][2]);
                    dpp[i + j][0] = min(dpp[i + j][0], dp[g][i][0] + dp[to][j][1]);
                    dpp[i + j][0] = min(dpp[i + j][0], dp[g][i][0] + dp[to][j][0]);
                }
            }
            ma[g] += ma[to];
            for (int i = 0; i <= ma[g]; i++)
            {
                dp[g][i][0] = min(dp[g][i][0], dpp[i][0]);
                dp[g][i][1] = min(dp[g][i][1], dpp[i][1]);
                dp[g][i][2] = min(dp[g][i][2], dpp[i][2]);
            }
        }
    }
}

void solve()
{
    int i, j, m, x, y, q;
    cin >> n >> m;
    for ( i = 0; i <= n + 1; i++)
    {
        for ( j = 0; j <= n + 1; j++)
        {
            dp[i][j][0] = 1e15;
            dp[i][j][1] = 1e15;
            dp[i][j][2] = 1e15;
        }
    }
    for ( i = 1; i <= n; i++)
    {
        cin >> d[i];
    }
    for ( i = 0; i < m; i++)
    {
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    d[n + 1] = 1e15;
    for ( i = 1; i <= n; i++)
    {
        if (color[i] == 0)
        {
            Dfs(i, -1);
            v[n + 1].push_back(i);
        }
    }
    Dfs(n + 1, -1);
    cin >> q;
    for ( i = 0; i < q; i++)
    {
        cin >> x;
        int l = 2, r = n + 1;
        int ans = 0;
        while (l <= r)
        {
            m = (l + r) / 2;
            if (dp[n + 1][m][0] <= x)
            {
                ans = m;
                l = m + 1;
            }
            else
            {
                r = m - 1;
            }
        }
        cout << ans << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

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