oj.uz

Submission #747143

# Submission time Handle Problem Language Result Execution time Memory
747143 2023-05-23T17:13:21 Z MilosMilutinovic Džumbus (COCI19_dzumbus) C++14
110 / 110
 314 ms 31028 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1010;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, m, q, d[N], sz[N];
vector<int> g[N];
ll dp[N][N][3], ndp[N][N][3], ans[N], nans[N];
bool was[N];
void solve(int x, int fa) {
    was[x] = true;
    dp[x][0][0] =  0;
    dp[x][0][1] =  d[x];
    sz[x] = 1;
    for (int y : g[x]) {
        if (y == fa) continue;
        solve(y, x);
        for (int i = 0; i <= sz[x]; i++)
            for (int k = 0; k < 3; k++)
                ndp[x][i][k] = dp[x][i][k];
        for (int i = 0; i <= sz[x]; i++) {
            for (int j = 0; j <= sz[y]; j++) {

                dp[x][i + j][0] = min(dp[x][i + j][0], ndp[x][i][0] + dp[y][j][0]);
                dp[x][i + j][0] = min(dp[x][i + j][0], ndp[x][i][0] + dp[y][j][1]);
                dp[x][i + j][0] = min(dp[x][i + j][0], ndp[x][i][0] + dp[y][j][2]);

                dp[x][i + j][1] = min(dp[x][i + j][1], ndp[x][i][1] + dp[y][j][0]);
                dp[x][i + j][1] = min(dp[x][i + j][1], ndp[x][i][1] + dp[y][j][1]);
                dp[x][i + j][1] = min(dp[x][i + j][1], ndp[x][i][1] + dp[y][j][2]);

                dp[x][i + j][2] = min(dp[x][i + j][2], ndp[x][i][2] + dp[y][j][0]);
                dp[x][i + j + 1][2] = min(dp[x][i + j + 1][2], ndp[x][i][2] + dp[y][j][1]);
                dp[x][i + j][2] = min(dp[x][i + j][2], ndp[x][i][2] + dp[y][j][2]);

                dp[x][i + j + 1][2] = min(dp[x][i + j + 1][2], ndp[x][i][1] + dp[y][j][2]);
                dp[x][i + j + 2][2] = min(dp[x][i + j + 2][2], ndp[x][i][1] + dp[y][j][1]);
            }
        }
        sz[x] += sz[y];
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &d[i]);
    for (int i = 1; i <= m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= n; j++)
            for (int k = 0; k < 3; k++)
                dp[i][j][k] = inf;
    int cur_sz = 0;
    for (int i = 0; i < N; i++) ans[i] = inf;
    ans[0] = 0;
    for (int i = 1; i <= n; i++) if (!was[i]) {
        solve(i, i);
        for (int j = 0; j < N; j++) nans[j] = inf;
        for (int j = 0; j <= cur_sz; j++)
            for (int k = 0; k <= sz[i]; k++)
                nans[j + k] = min(nans[j + k], ans[j] + min({dp[i][k][0], dp[i][k][1], dp[i][k][2]}));
        for (int j = 0; j < N; j++) ans[j] = min(ans[j], nans[j]);
        cur_sz += sz[i];
    }
    vector<pair<ll, int>> f;
    for (int i = 0; i < N; i++) f.emplace_back(ans[i], i);
    sort(f.begin(), f.end());
    for (int i = 1; i < (int) f.size(); i++) f[i].second = max(f[i].second, f[i - 1].second);
    scanf("%d", &q);
    while (q--) {
        int s;
        scanf("%d", &s);
        int r = 0;
        for (auto& p : f) if (p.first <= s) r = max(r, p.second);
        printf("%d\n", r);
    }
    return 0;
}

Compilation message

dzumbus.cpp: In function 'int main()':
dzumbus.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
dzumbus.cpp:45:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     for (int i = 1; i <= n; i++) scanf("%d", &d[i]);
      |                                  ~~~~~^~~~~~~~~~~~~
dzumbus.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         scanf("%d%d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~
dzumbus.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
dzumbus.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         scanf("%d", &s);
      |         ~~~~~^~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28244 KB Output is correct
2 Correct 22 ms 28268 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28244 KB Output is correct
2 Correct 22 ms 28268 KB Output is correct
3 Correct 271 ms 30460 KB Output is correct
4 Correct 259 ms 31028 KB Output is correct
5 Correct 225 ms 30608 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 3284 KB Output is correct
2 Correct 212 ms 3076 KB Output is correct
3 Correct 196 ms 3528 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28244 KB Output is correct
2 Correct 22 ms 28268 KB Output is correct
3 Correct 271 ms 30460 KB Output is correct
4 Correct 259 ms 31028 KB Output is correct
5 Correct 225 ms 30608 KB Output is correct
6 Correct 185 ms 3284 KB Output is correct
7 Correct 212 ms 3076 KB Output is correct
8 Correct 196 ms 3528 KB Output is correct
9 Correct 314 ms 28976 KB Output is correct
10 Correct 267 ms 29112 KB Output is correct
11 Correct 217 ms 28292 KB Output is correct