oj.uz

Submission #1104418

# Submission time Handle Problem Language Result Execution time Memory
1104418 2024-10-23T17:24:20 Z f0rizen Museum (CEOI17_museum) C++17
0 / 100
 165 ms 15284 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<vector<int>>> 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, vector<int>(2, inf));
    dp[v][1][0] = 0;
    dp[v][1][1] = 0;
    int cur = 1;
    for (auto [u, w] : g[v]) {
        if (u != p) {
            vector<vector<int>> dpp(cur + sz[u] + 1, vector<int>(2, 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][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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 165 ms 15284 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 165 ms 15284 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -