oj.uz

Submission #912722

# Submission time Handle Problem Language Result Execution time Memory
912722 2024-01-19T18:56:06 Z CyberCow Džumbus (COCI19_dzumbus) C++17
110 / 110
 41 ms 27156 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24412 KB Output is correct
2 Correct 10 ms 24412 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24412 KB Output is correct
2 Correct 10 ms 24412 KB Output is correct
3 Correct 40 ms 26460 KB Output is correct
4 Correct 41 ms 27156 KB Output is correct
5 Correct 40 ms 26708 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6484 KB Output is correct
2 Correct 28 ms 6484 KB Output is correct
3 Correct 29 ms 6748 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24412 KB Output is correct
2 Correct 10 ms 24412 KB Output is correct
3 Correct 40 ms 26460 KB Output is correct
4 Correct 41 ms 27156 KB Output is correct
5 Correct 40 ms 26708 KB Output is correct
6 Correct 27 ms 6484 KB Output is correct
7 Correct 28 ms 6484 KB Output is correct
8 Correct 29 ms 6748 KB Output is correct
9 Correct 40 ms 26152 KB Output is correct
10 Correct 39 ms 26964 KB Output is correct
11 Correct 40 ms 26604 KB Output is correct