oj.uz

Submission #1104420

# Submission time Handle Problem Language Result Execution time Memory
1104420 2024-10-23T17:28:28 Z f0rizen Museum (CEOI17_museum) C++17
100 / 100
 323 ms 172060 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;

template<typename T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i : a) {
        is >> i;
    }
    return is;
}

struct Edge {
    int to, w;
};

vector<vector<Edge>> g;
vector<int> sz;
vector<vector<array<int, 2>>> dp;

void dfs(int v, int p = -1) {
    sz[v] = 1;
    for (auto [u, w] : g[v]) {
        if (u != p) {
            dfs(u, v);
            sz[v] += sz[u];
        }
    }
    dp[v].resize(2);
    for (int i = 0; i < 2; ++i) {
        dp[v][i][0] = inf;
        dp[v][i][0] = inf;
    }
    dp[v][1][0] = 0;
    dp[v][1][1] = 0;
    int cur = 1;
    for (auto [u, w] : g[v]) {
        if (u != p) {
            vector<array<int, 2>> dpp(cur + sz[u] + 1);
            for (int i = 0; i <= cur + sz[u]; ++i) {
                dpp[i][0] = inf;
                dpp[i][1] = inf;
            }
            for (int i = 0; i <= cur; ++i) {
                for (int j = 0; j <= sz[u]; ++j) {
                    if (j == 0) {
                        dpp[i + j][0] = min(dpp[i + j][0], dp[v][i][0]);
                        dpp[i + j][1] = min(dpp[i + j][1], dp[v][i][1]);
                    } else {
                        dpp[i + j][0] = min(dpp[i + j][0], dp[v][i][1] + dp[u][j][0] + w);
                        dpp[i + j][0] = min(dpp[i + j][0], dp[v][i][0] + dp[u][j][1] + 2 * w);
                        dpp[i + j][1] = min(dpp[i + j][1], dp[v][i][1] + dp[u][j][1] + 2 * w);
                    }
                }
            }
            dp[v] = dpp;
            cur += sz[u];
        }
    }
}

int32_t main() {
#ifdef LOCAL
    freopen("/tmp/input.txt", "r", stdin);
#else
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int n, k, x;
    cin >> n >> k >> x;
    --x;
    g.resize(n);
    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    sz.resize(n);
    dp.resize(n);
    dfs(x);
    cout << dp[x][k][0] << "\n";
    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 4068 KB Output is correct
2 Correct 121 ms 4424 KB Output is correct
3 Correct 323 ms 172060 KB Output is correct
4 Correct 182 ms 53832 KB Output is correct
5 Correct 130 ms 13212 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 4068 KB Output is correct
2 Correct 121 ms 4424 KB Output is correct
3 Correct 323 ms 172060 KB Output is correct
4 Correct 182 ms 53832 KB Output is correct
5 Correct 130 ms 13212 KB Output is correct
6 Correct 125 ms 2864 KB Output is correct
7 Correct 237 ms 99912 KB Output is correct
8 Correct 281 ms 2160 KB Output is correct
9 Correct 241 ms 2460 KB Output is correct
10 Correct 129 ms 3148 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 116 ms 4068 KB Output is correct
7 Correct 121 ms 4424 KB Output is correct
8 Correct 323 ms 172060 KB Output is correct
9 Correct 182 ms 53832 KB Output is correct
10 Correct 130 ms 13212 KB Output is correct
11 Correct 125 ms 2864 KB Output is correct
12 Correct 237 ms 99912 KB Output is correct
13 Correct 281 ms 2160 KB Output is correct
14 Correct 241 ms 2460 KB Output is correct
15 Correct 129 ms 3148 KB Output is correct
16 Correct 118 ms 4680 KB Output is correct
17 Correct 120 ms 4620 KB Output is correct
18 Correct 199 ms 65364 KB Output is correct
19 Correct 246 ms 2396 KB Output is correct
20 Correct 120 ms 2896 KB Output is correct
21 Correct 222 ms 93512 KB Output is correct
22 Correct 116 ms 4076 KB Output is correct
23 Correct 233 ms 2352 KB Output is correct
24 Correct 117 ms 3152 KB Output is correct
25 Correct 301 ms 164308 KB Output is correct