oj.uz

Submission #1095004

# Submission time Handle Problem Language Result Execution time Memory
1095004 2024-10-01T07:08:44 Z blackslex Museum (CEOI17_museum) C++17
100 / 100
 736 ms 784468 KB 
#include<bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

const int N = 1e4 + 5;
int n, k, c, x, y, z, sz[N], dp[N][2][N];
vector<pii> v[N];

void dfs (int cur, int par) {
    sz[cur] = 1;
    for (auto &[x, y]: v[cur]) {
        if (par == x) continue;
        dfs(x, cur);
        for (int i = sz[cur]; ~i; i--) {
            for (int j = sz[x]; ~j; j--) {
                dp[cur][0][i + j] = min(dp[cur][0][i + j], dp[cur][1][i] + dp[x][0][j] + y);
                dp[cur][0][i + j] = min(dp[cur][0][i + j], dp[cur][0][i] + dp[x][1][j] + y * 2);
                dp[cur][1][i + j] = min(dp[cur][1][i + j], dp[cur][1][i] + dp[x][1][j] + y * 2);
            }
        }
        sz[cur] += sz[x];
    }
}

int main() {
    scanf("%d %d %d", &n, &k, &c);
    for (int i = 1; i < n; i++) {
        scanf("%d %d %d", &x, &y, &z);
        v[x].emplace_back(y, z); v[y].emplace_back(x, z);
    }
    for (int i = 1; i <= n; i++) {
        for (auto j: {0, 1}) {
            for (int k = 2; k <= n; k++) dp[i][j][k] = 1e9;
        }
    }
    dfs(c, 0);
    printf("%d", min(dp[c][0][k], dp[c][1][k]));
}

Compilation message

museum.cpp: In function 'int main()':
museum.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf("%d %d %d", &n, &k, &c);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
museum.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         scanf("%d %d %d", &x, &y, &z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 784188 KB Output is correct
2 Correct 466 ms 784212 KB Output is correct
3 Correct 548 ms 784468 KB Output is correct
4 Correct 506 ms 784240 KB Output is correct
5 Correct 479 ms 784392 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 784188 KB Output is correct
2 Correct 466 ms 784212 KB Output is correct
3 Correct 548 ms 784468 KB Output is correct
4 Correct 506 ms 784240 KB Output is correct
5 Correct 479 ms 784392 KB Output is correct
6 Correct 472 ms 784356 KB Output is correct
7 Correct 497 ms 784464 KB Output is correct
8 Correct 736 ms 784208 KB Output is correct
9 Correct 637 ms 784208 KB Output is correct
10 Correct 469 ms 784212 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 477 ms 784188 KB Output is correct
7 Correct 466 ms 784212 KB Output is correct
8 Correct 548 ms 784468 KB Output is correct
9 Correct 506 ms 784240 KB Output is correct
10 Correct 479 ms 784392 KB Output is correct
11 Correct 472 ms 784356 KB Output is correct
12 Correct 497 ms 784464 KB Output is correct
13 Correct 736 ms 784208 KB Output is correct
14 Correct 637 ms 784208 KB Output is correct
15 Correct 469 ms 784212 KB Output is correct
16 Correct 475 ms 784212 KB Output is correct
17 Correct 454 ms 784212 KB Output is correct
18 Correct 516 ms 784468 KB Output is correct
19 Correct 725 ms 784404 KB Output is correct
20 Correct 484 ms 784464 KB Output is correct
21 Correct 534 ms 784468 KB Output is correct
22 Correct 477 ms 784392 KB Output is correct
23 Correct 676 ms 784212 KB Output is correct
24 Correct 456 ms 784212 KB Output is correct
25 Correct 552 ms 784468 KB Output is correct