oj.uz

답안 #1104419

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1104419 2024-10-23T17:26:16 Z f0rizen Museum (CEOI17_museum) C++17
45 / 100
 3000 ms 944112 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][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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 183 ms 15080 KB Output is correct
2 Correct 191 ms 17000 KB Output is correct
3 Correct 2355 ms 944112 KB Output is correct
4 Correct 900 ms 300776 KB Output is correct
5 Correct 331 ms 76944 KB Output is correct

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 183 ms 15080 KB Output is correct
2 Correct 191 ms 17000 KB Output is correct
3 Correct 2355 ms 944112 KB Output is correct
4 Correct 900 ms 300776 KB Output is correct
5 Correct 331 ms 76944 KB Output is correct
6 Correct 190 ms 10152 KB Output is correct
7 Correct 1498 ms 551604 KB Output is correct
8 Execution timed out 3056 ms 4512 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 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 183 ms 15080 KB Output is correct
7 Correct 191 ms 17000 KB Output is correct
8 Correct 2355 ms 944112 KB Output is correct
9 Correct 900 ms 300776 KB Output is correct
10 Correct 331 ms 76944 KB Output is correct
11 Correct 190 ms 10152 KB Output is correct
12 Correct 1498 ms 551604 KB Output is correct
13 Execution timed out 3056 ms 4512 KB Time limit exceeded
14 Halted 0 ms 0 KB -