oj.uz

Submission #998613

# Submission time Handle Problem Language Result Execution time Memory
998613 2024-06-14T10:49:34 Z NoLove Museum (CEOI17_museum) C++14
100 / 100
 470 ms 784980 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;
    for (auto[u, w] : adj[v]) {
        if (u == prv) continue;
        dfs(u, v);
        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);
            }
        }
        sz[v] += sz[u];
    }
}
main() {
    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:18:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |     for (auto[u, w] : adj[v]) {
      |              ^
museum.cpp: At global scope:
museum.cpp:31:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   31 | main() {
      | ^~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 784176 KB Output is correct
2 Correct 301 ms 784208 KB Output is correct
3 Correct 311 ms 784124 KB Output is correct
4 Correct 311 ms 784212 KB Output is correct
5 Correct 310 ms 784076 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 784792 KB Output is correct
2 Correct 390 ms 784636 KB Output is correct
3 Correct 311 ms 784976 KB Output is correct
4 Correct 310 ms 784852 KB Output is correct
5 Correct 326 ms 784720 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 784792 KB Output is correct
2 Correct 390 ms 784636 KB Output is correct
3 Correct 311 ms 784976 KB Output is correct
4 Correct 310 ms 784852 KB Output is correct
5 Correct 326 ms 784720 KB Output is correct
6 Correct 322 ms 784696 KB Output is correct
7 Correct 319 ms 784980 KB Output is correct
8 Correct 316 ms 784724 KB Output is correct
9 Correct 313 ms 784720 KB Output is correct
10 Correct 318 ms 784720 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 784176 KB Output is correct
2 Correct 301 ms 784208 KB Output is correct
3 Correct 311 ms 784124 KB Output is correct
4 Correct 311 ms 784212 KB Output is correct
5 Correct 310 ms 784076 KB Output is correct
6 Correct 324 ms 784792 KB Output is correct
7 Correct 390 ms 784636 KB Output is correct
8 Correct 311 ms 784976 KB Output is correct
9 Correct 310 ms 784852 KB Output is correct
10 Correct 326 ms 784720 KB Output is correct
11 Correct 322 ms 784696 KB Output is correct
12 Correct 319 ms 784980 KB Output is correct
13 Correct 316 ms 784724 KB Output is correct
14 Correct 313 ms 784720 KB Output is correct
15 Correct 318 ms 784720 KB Output is correct
16 Correct 335 ms 784788 KB Output is correct
17 Correct 376 ms 784720 KB Output is correct
18 Correct 343 ms 784720 KB Output is correct
19 Correct 341 ms 784720 KB Output is correct
20 Correct 340 ms 784468 KB Output is correct
21 Correct 444 ms 784720 KB Output is correct
22 Correct 402 ms 784468 KB Output is correct
23 Correct 446 ms 784468 KB Output is correct
24 Correct 394 ms 784468 KB Output is correct
25 Correct 470 ms 784980 KB Output is correct