oj.uz

Submission #998733

# Submission time Handle Problem Language Result Execution time Memory
998733 2024-06-14T15:26:55 Z NoLove Džumbus (COCI19_dzumbus) C++14
0 / 110
 255 ms 18244 KB 
/**
 *    author : Lăng Trọng Đạt
 *    created: 14-06-2024 
**/
#include <bits/stdc++.h>
using namespace std;
#define int long long
void mi(int& a, int b) { if (b < a) a = b; }

const int MAXN = 1000 + 5;
vector<int> adj[MAXN];
int g[MAXN];
int n, m, a, b;
int dp[MAXN][MAXN][2];
// 0 là chưa say
// 1 là đã chia sẻ

int sz[MAXN];
void dfs(int v, int prv) {
    dp[v][0][1] = g[v];
    dp[v][0][0] = 0;
    sz[v] = 1;
    for (int u : adj[v]) {
        if (u == prv) continue;
        dfs(u, v);
        // t = 0
        for (int k = sz[v] + sz[u]; k >= 0; k--) {
            for (int j = max(0LL, k - sz[v]); j <= min(k, sz[u]); j++) {
                mi(dp[v][k + 2][1], dp[v][k - j][0] + dp[u][j][0] + g[u] + g[v]);
                if (k - j != 0)
                    mi(dp[v][k + 1][1], dp[v][k - j][1] + dp[u][j][0] + g[u]);
                if (j != 0)
                    mi(dp[v][k + 1][1], dp[v][k - j][0] + dp[u][j][1] + g[v]);
                mi(dp[v][k][0], min(dp[v][k - j][0], dp[v][k - j][1]) + min(dp[u][j][1], dp[u][j][0]));
            }
        }
        sz[v] += sz[u];
    }
}
main() {
    // freopen("hi.inp", "r", stdin);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> g[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    memset(dp, 0x3f, sizeof(dp));

    dfs(1, -1);
    map<int, int> mp;
    mp[-1] = 0;
    auto add = [&](int s, int i) -> void {
        if (mp.count(s)) mp[s] = max(mp[s], i);
        else mp[s] = i;
    };
    for (int i = 1; i <= n; i++) {
        add(dp[1][i][0], i);
        add(dp[1][i][1], i);
    }
    int q, x;
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> x;
        auto it = mp.upper_bound(x);
        cout << prev(it)->second << "\n";
    }
}

Compilation message

dzumbus.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main() {
      | ^~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16472 KB Output is correct
2 Incorrect 6 ms 16472 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16472 KB Output is correct
2 Incorrect 6 ms 16472 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 255 ms 18244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16472 KB Output is correct
2 Incorrect 6 ms 16472 KB Output isn't correct
3 Halted 0 ms 0 KB -