제출 #1256374

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256374		iamhereforfun	Džumbus (COCI19_dzumbus)	C++20	110 / 110	35 ms	32840 KiB

dzumbus

// Starcraft 2 enjoyer + luv kd //

#include <bits/stdc++.h>

using namespace std;

#define LSOne(X) ((X) & -(X))

const int N = 1e3 + 5;
const int M = 4e5 + 5;
const int S = 640;
const int O = 2e5 + 5;
const int K = 15;
const int LG = 21;
const int P = 37;
const long long INF = 1e18 + 5;
const int MOD = 1e9 + 7;
const int nx[] = {0, 1, 0, -1}, ny[] = {1, 0, -1, 0};

int n, m, d[N], sz[N], q;
long long ans[N], dp[N][N][2][2];
vector<int> adj[N], root;
bool vis[N];

void dfs(int c, int p)
{
    sz[c] = 1;
    vis[c] = 1;
    dp[c][0][0][0] = 0;
    dp[c][0][1][0] = d[c];
    for (int i : adj[c])
    {
        if (i == p)
            continue;
        dfs(i, c);
        for (int x = sz[c]; x >= 0; x--)
        {
            for (int y = sz[i]; y >= 0; y--)
            {
                if (x + y <= n)
                {
                    dp[c][x + y][0][0] = min(dp[c][x + y][0][0], dp[c][x][0][0] + dp[i][y][0][0]);
                    if (x > 0 && y > 0)
                        dp[c][x + y][1][1] = min(dp[c][x + y][1][1], dp[c][x - 1][1][0] + min(dp[i][y - 1][1][0], dp[i][y][1][1]));
                    if (y > 0)
                        dp[c][x + y][1][1] = min(dp[c][x + y][1][1], dp[c][x][1][1] + min(dp[i][y - 1][1][0], dp[i][y][1][1]));
                    dp[c][x + y][1][1] = min(dp[c][x + y][1][1], dp[c][x][1][1] + dp[i][y][0][0]);
                    dp[c][x + y][1][0] = min(dp[c][x + y][1][0], dp[c][x][1][0] + dp[i][y][0][0]);
                    dp[c][x + y][0][0] = min(dp[c][x + y][0][0], min(dp[c][x + y][1][0], dp[c][x + y][1][1]));
                    // cout << dp[c][x + y][1][1] << " " << c << " " << i << " " << x << " " << y << "a\n";
                }
            }
        }
        sz[c] += sz[i];
    }
    // cout << c << "\n";
    // for (int x = 0; x <= sz[c]; x++)
    // {
    //     cout << dp[c][x][0][0] << " " << dp[c][x][1][0] << " " << dp[c][x][1][1] << " " << x << "\n";
    //     dp[c][x][0][0] = min(dp[c][x][0][0], min(dp[c][x][1][0], dp[c][x][1][1]));
    // }
}

void solve()
{
    cin >> n >> m;
    for (int x = 1; x <= n; x++)
    {
        cin >> d[x];
        ans[x] = INF;
    }
    ans[n + 1] = INF;
    for (int x = 0; x <= n; x++)
    {
        for (int y = 0; y <= n; y++)
        {
            dp[x][y][0][0] = INF;
            dp[x][y][1][0] = INF;
            dp[x][y][1][1] = INF;
        }
    }
    for (int x = 0; x < m; x++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int x = 1; x <= n; x++)
    {
        if (vis[x])
            continue;
        root.push_back(x);
        dfs(x, 0);
    }
    for(int x = 1; x < root.size(); x++)
    {
        int c = root[0], i = root[x];
        dp[c][0][0][0] = 0;
        for (int x = sz[c]; x >= 0; x--)
        {
            for (int y = sz[i]; y >= 0; y--)
            {
                if (x + y <= n)
                {
                    dp[c][x + y][0][0] = min(dp[c][x + y][0][0], dp[c][x][0][0] + dp[i][y][0][0]);
                }
            }
        }
        sz[c] += sz[i];
    }
    for (int x = n; x >= 0; x--)
    {
        int c = root[0];
        dp[c][x][0][0] = min(dp[c][x][0][0], dp[c][x][1][0]);
        dp[c][x][0][0] = min(dp[c][x][0][0], dp[c][x][1][1]);
        ans[x] = dp[c][x][0][0];
        ans[x] = min(ans[x], ans[x + 1]);
        // cout << ans[x] << " " << x << "\n";
    }
    cin >> q;
    for (int x = 0; x < q; x++)
    {
        int i;
        cin >> i;
        cout << upper_bound(ans, ans + n + 1, i) - ans - 1 << "\n";
    }
}

signed main()
{
    // freopen("CP.INP", "r", stdin);
    // freopen("CP.OUT", "w", stdout);
    // freopen("art2.in", "r", stdin);
    // freopen("art2.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}

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