oj.uz

Submission #533625

# Submission time Handle Problem Language Result Execution time Memory
533625 2022-03-06T16:40:48 Z zxcvbnm Museum (CEOI17_museum) C++14
100 / 100
 693 ms 784712 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int nax = 10005;
constexpr int INF = 1e9 + 5;
int dp[nax][nax][2];
int sz[nax];
vector<pair<int, int>> adj[nax];

void self_min(int& me, int other) {
    me = min(me, other);
}

void dfs(int v, int p) {
    dp[v][1][0] = dp[v][1][1] = 0;
    sz[v] = 1;

    for(auto& child : adj[v]) {
        int u = child.first, w = child.second;
        if (u == p) continue;
        dfs(u, v);

        for(int i = sz[v]; i >= 0; i--) {
            for(int j = sz[u]; j >= 0; j--) {
                self_min(dp[v][i+j][0], dp[v][i][0]+dp[u][j][0]+2*w);
                self_min(dp[v][i+j][1], dp[v][i][1]+dp[u][j][0]+2*w);
                self_min(dp[v][i+j][1], dp[v][i][0]+dp[u][j][1]+w);
            }
        }
        sz[v] += sz[u];
    }

//    cout << v << " " << sz[v] << ": \n";
//    for(int i = 0; i <= sz[v]; i++) {
//        cout << i << ": " << dp[v][i][0] << " " << dp[v][i][1] << "\n";
//    }
//    cout << "--\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k, x;
    cin >> n >> k >> x;
    for(int i = 0; i < n-1; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }

    for(int i = 0; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            for(int p = 0; p < 2; p++) {
                dp[i][j][p] = INF;
            }
        }
    }

    dfs(x, -1);
    cout << dp[x][k][1] << "\n";
    return 0;
}
/*

11 8 3
1 3 3
3 2 5
6 4 5
1 11 3
9 1 2
9 10 2
3 7 10
6 7 1
7 8 1
7 5 1


*/

Subtask #1
20.0 / 20.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 784364 KB Output is correct
2 Correct 482 ms 784468 KB Output is correct
3 Correct 541 ms 784580 KB Output is correct
4 Correct 511 ms 784524 KB Output is correct
5 Correct 488 ms 784364 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 784364 KB Output is correct
2 Correct 482 ms 784468 KB Output is correct
3 Correct 541 ms 784580 KB Output is correct
4 Correct 511 ms 784524 KB Output is correct
5 Correct 488 ms 784364 KB Output is correct
6 Correct 484 ms 784272 KB Output is correct
7 Correct 532 ms 784696 KB Output is correct
8 Correct 693 ms 784312 KB Output is correct
9 Correct 629 ms 784348 KB Output is correct
10 Correct 497 ms 784344 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 517 ms 784364 KB Output is correct
7 Correct 482 ms 784468 KB Output is correct
8 Correct 541 ms 784580 KB Output is correct
9 Correct 511 ms 784524 KB Output is correct
10 Correct 488 ms 784364 KB Output is correct
11 Correct 484 ms 784272 KB Output is correct
12 Correct 532 ms 784696 KB Output is correct
13 Correct 693 ms 784312 KB Output is correct
14 Correct 629 ms 784348 KB Output is correct
15 Correct 497 ms 784344 KB Output is correct
16 Correct 498 ms 784360 KB Output is correct
17 Correct 476 ms 784340 KB Output is correct
18 Correct 518 ms 784488 KB Output is correct
19 Correct 634 ms 784328 KB Output is correct
20 Correct 491 ms 784308 KB Output is correct
21 Correct 528 ms 784572 KB Output is correct
22 Correct 495 ms 784456 KB Output is correct
23 Correct 626 ms 784372 KB Output is correct
24 Correct 486 ms 784380 KB Output is correct
25 Correct 549 ms 784712 KB Output is correct