oj.uz

Submission #998608

# Submission time Handle Problem Language Result Execution time Memory
998608 2024-06-14T10:46:12 Z NoLove Museum (CEOI17_museum) C++14
100 / 100
 490 ms 785080 KB 
/**
 *    author : Lăng Trọng Đạt
 *    created: 14-06-2024 
**/
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e4 + 5;
int sz[MAXN];
vector<pair<int, int>> adj[MAXN];
int dp[MAXN][MAXN][2];
int n, k, s;

void dfs(int v, int prv = -1) {
    sz[v] = 1;
    dp[v][1][0] = dp[v][1][1] = 0;
    dp[v][0][0] = dp[v][0][1] = 0;
    // db(dp[v][2][1])
    for (auto[u, w] : adj[v]) {
        if (u == prv) continue;
        dfs(u, v);
        // db(v, u, w)
        for (int i = min(k, sz[v] + sz[u]); i > 0; i--) {
            for (int j = max(1, i - sz[v]); j <= min(i, sz[u]); j++) {
                dp[v][i][1] = min(dp[v][i][1], dp[v][i - j][1] + dp[u][j][1] + 2*w);
                dp[v][i][0] = min(dp[v][i][0], dp[v][i - j][0] + dp[u][j][1] + 2*w);
                dp[v][i][0] = min(dp[v][i][0], dp[v][i - j][1] + dp[u][j][0] + w);
                // if (v == 1 && i == 3 && dp[1][3][1] == 0) {
                //     db(j, u, w, dp[u][j][1])
                // }
            }
        }
        sz[v] += sz[u];
    }
    // db(v)
    // for (int i = 1; i <= sz[v]; i++) {
    //     db(i, dp[v][i][1])
    // }
}
main() {
    iostream::sync_with_stdio(0);
    cin.tie(0);
    // freopen("hi.inp", "r", stdin);
    
    memset(dp, 0x3f, sizeof(dp));
    cin >> n >> k >> s;
    int a, b, w;
    for (int i = 1; i < n; i++) {
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    
    dfs(s);
    cout << dp[s][k][0];
}

Compilation message

museum.cpp: In function 'void dfs(int, int)':
museum.cpp:19:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |     for (auto[u, w] : adj[v]) {
      |              ^
museum.cpp: At global scope:
museum.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main() {
      | ^~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 784212 KB Output is correct
2 Correct 307 ms 784212 KB Output is correct
3 Correct 311 ms 784152 KB Output is correct
4 Correct 303 ms 784208 KB Output is correct
5 Correct 301 ms 784040 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 784552 KB Output is correct
2 Correct 303 ms 784468 KB Output is correct
3 Correct 314 ms 784980 KB Output is correct
4 Correct 308 ms 784880 KB Output is correct
5 Correct 314 ms 784744 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 784552 KB Output is correct
2 Correct 303 ms 784468 KB Output is correct
3 Correct 314 ms 784980 KB Output is correct
4 Correct 308 ms 784880 KB Output is correct
5 Correct 314 ms 784744 KB Output is correct
6 Correct 317 ms 784720 KB Output is correct
7 Correct 313 ms 784976 KB Output is correct
8 Correct 311 ms 784720 KB Output is correct
9 Correct 317 ms 784720 KB Output is correct
10 Correct 314 ms 784724 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 784212 KB Output is correct
2 Correct 307 ms 784212 KB Output is correct
3 Correct 311 ms 784152 KB Output is correct
4 Correct 303 ms 784208 KB Output is correct
5 Correct 301 ms 784040 KB Output is correct
6 Correct 313 ms 784552 KB Output is correct
7 Correct 303 ms 784468 KB Output is correct
8 Correct 314 ms 784980 KB Output is correct
9 Correct 308 ms 784880 KB Output is correct
10 Correct 314 ms 784744 KB Output is correct
11 Correct 317 ms 784720 KB Output is correct
12 Correct 313 ms 784976 KB Output is correct
13 Correct 311 ms 784720 KB Output is correct
14 Correct 317 ms 784720 KB Output is correct
15 Correct 314 ms 784724 KB Output is correct
16 Correct 329 ms 784720 KB Output is correct
17 Correct 366 ms 784720 KB Output is correct
18 Correct 438 ms 784864 KB Output is correct
19 Correct 363 ms 785040 KB Output is correct
20 Correct 323 ms 784724 KB Output is correct
21 Correct 490 ms 784820 KB Output is correct
22 Correct 412 ms 784724 KB Output is correct
23 Correct 474 ms 784612 KB Output is correct
24 Correct 397 ms 784688 KB Output is correct
25 Correct 460 ms 785080 KB Output is correct