oj.uz

Submission #977965

# Submission time Handle Problem Language Result Execution time Memory
977965 2024-05-08T15:08:12 Z Beerus13 Museum (CEOI17_museum) C++14
100 / 100
 433 ms 785020 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
const int N = 1e4 + 5;
const int inf = 1e9;

bool minimize(auto &a, auto b) {
    if(a <= b) return true;
    a = b;
    return false;
}

int n, k, x, sz[N];
int dp[2][N][N];
// 0: don't return to starting point
vector<pii> g[N];

void dfs(int u, int p = 0) {
    sz[u] = 1;
    dp[0][u][0] = dp[0][u][1] = 0;
    dp[1][u][0] = dp[1][u][1] = 0;
    for(auto [v, w] : g[u]) if(v != p) {
        dfs(v, u);
        for(int i = sz[u]; i >= 0; --i) {
            for(int j = 0; j <= sz[v]; ++j) {
                minimize(dp[0][u][i + j], dp[1][u][i] + dp[0][v][j] + w);
                minimize(dp[0][u][i + j], dp[0][u][i] + dp[1][v][j] + 2 * w);
                minimize(dp[1][u][i + j], dp[1][u][i] + dp[1][v][j] + 2 * w);
            }
        }
        sz[u] += sz[v];
    }
}

void solve() {
    cin >> n >> k >> x;
    for(int i = 1, u, v, w; i < n; ++i) {
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    memset(dp, 0x3f, sizeof(dp));
    dfs(x);
    cout << dp[0][x][k] << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int test = 1;
    // cin >> test;
    while(test--) solve();
    return 0;
}

Compilation message

museum.cpp:8:15: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    8 | bool minimize(auto &a, auto b) {
      |               ^~~~
museum.cpp:8:24: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    8 | bool minimize(auto &a, auto b) {
      |                        ^~~~
museum.cpp: In function 'void dfs(int, int)':
museum.cpp:23:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |     for(auto [v, w] : g[u]) if(v != p) {
      |              ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 784144 KB Output is correct
2 Correct 186 ms 784180 KB Output is correct
3 Correct 167 ms 784208 KB Output is correct
4 Correct 153 ms 784000 KB Output is correct
5 Correct 151 ms 784136 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 784744 KB Output is correct
2 Correct 222 ms 784812 KB Output is correct
3 Correct 254 ms 784972 KB Output is correct
4 Correct 225 ms 785020 KB Output is correct
5 Correct 230 ms 784888 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 784744 KB Output is correct
2 Correct 222 ms 784812 KB Output is correct
3 Correct 254 ms 784972 KB Output is correct
4 Correct 225 ms 785020 KB Output is correct
5 Correct 230 ms 784888 KB Output is correct
6 Correct 211 ms 784944 KB Output is correct
7 Correct 238 ms 784976 KB Output is correct
8 Correct 307 ms 784764 KB Output is correct
9 Correct 282 ms 784724 KB Output is correct
10 Correct 228 ms 784832 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 784144 KB Output is correct
2 Correct 186 ms 784180 KB Output is correct
3 Correct 167 ms 784208 KB Output is correct
4 Correct 153 ms 784000 KB Output is correct
5 Correct 151 ms 784136 KB Output is correct
6 Correct 228 ms 784744 KB Output is correct
7 Correct 222 ms 784812 KB Output is correct
8 Correct 254 ms 784972 KB Output is correct
9 Correct 225 ms 785020 KB Output is correct
10 Correct 230 ms 784888 KB Output is correct
11 Correct 211 ms 784944 KB Output is correct
12 Correct 238 ms 784976 KB Output is correct
13 Correct 307 ms 784764 KB Output is correct
14 Correct 282 ms 784724 KB Output is correct
15 Correct 228 ms 784832 KB Output is correct
16 Correct 212 ms 784724 KB Output is correct
17 Correct 225 ms 784812 KB Output is correct
18 Correct 224 ms 784832 KB Output is correct
19 Correct 286 ms 784816 KB Output is correct
20 Correct 222 ms 784852 KB Output is correct
21 Correct 238 ms 784924 KB Output is correct
22 Correct 213 ms 784720 KB Output is correct
23 Correct 275 ms 784724 KB Output is correct
24 Correct 214 ms 784832 KB Output is correct
25 Correct 247 ms 785004 KB Output is correct