답안 #998731

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
998731 2024-06-14T15:26:24 Z NoLove Džumbus (COCI19_dzumbus) C++14
컴파일 오류
0 ms 0 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
        db(v, u)
        for (int k = sz[v] + sz[u]; k >= 0; k--) {
            db(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);
        db(i, dp[1][i][0], dp[1][i][1])
    }
    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: In function 'void dfs(long long int, long long int)':
dzumbus.cpp:27:9: error: 'db' was not declared in this scope; did you mean 'dp'?
   27 |         db(v, u)
      |         ^~
      |         dp
dzumbus.cpp:28:37: error: 'k' was not declared in this scope
   28 |         for (int k = sz[v] + sz[u]; k >= 0; k--) {
      |                                     ^
dzumbus.cpp: At global scope:
dzumbus.cpp:42:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   42 | main() {
      | ^~~~
dzumbus.cpp: In function 'int main()':
dzumbus.cpp:67:9: error: 'db' was not declared in this scope; did you mean 'dp'?
   67 |         db(i, dp[1][i][0], dp[1][i][1])
      |         ^~
      |         dp