oj.uz

Submission #998606

# Submission time Handle Problem Language Result Execution time Memory
998606 2024-06-14T10:43:46 Z NoLove Museum (CEOI17_museum) C++14
20 / 100
 3000 ms 784816 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 <= 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 315 ms 784148 KB Output is correct
2 Correct 295 ms 784208 KB Output is correct
3 Correct 290 ms 784212 KB Output is correct
4 Correct 267 ms 784080 KB Output is correct
5 Correct 290 ms 784052 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 784464 KB Output is correct
2 Correct 332 ms 784600 KB Output is correct
3 Execution timed out 3101 ms 784816 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 784464 KB Output is correct
2 Correct 332 ms 784600 KB Output is correct
3 Execution timed out 3101 ms 784816 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 784148 KB Output is correct
2 Correct 295 ms 784208 KB Output is correct
3 Correct 290 ms 784212 KB Output is correct
4 Correct 267 ms 784080 KB Output is correct
5 Correct 290 ms 784052 KB Output is correct
6 Correct 305 ms 784464 KB Output is correct
7 Correct 332 ms 784600 KB Output is correct
8 Execution timed out 3101 ms 784816 KB Time limit exceeded
9 Halted 0 ms 0 KB -