oj.uz

Submission #161447

# Submission time Handle Problem Language Result Execution time Memory
161447 2019-11-02T15:21:26 Z Minnakhmetov Museum (CEOI17_museum) C++14
80 / 100
 3000 ms 784880 KB 
#include <bits/stdc++.h>
    
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
 
using namespace std;

struct E {
    int to, w;
};

const int N = 1e4 + 5, K = N, INF = 1e9;
vector<E> g[N];
int dp[N][K][2];
int n, k, x;

void upd(int &x, int y) {
    x = min(x, y);
}

void dfs(int node, int h, int anc) {
    dp[node][1][0] = dp[node][1][1] = 0;

    for (E e : g[node]) {
        if (e.to != anc) {
            dfs(e.to, h + 1, node);

            for (int x = k - h; x > 0; x--) {
                for (int y = 1; x + y <= k - h; y++) {
                    upd(dp[node][x + y][0], dp[node][x][0] + dp[e.to][y][1] + e.w * 2);
                    upd(dp[node][x + y][0], dp[node][x][1] + dp[e.to][y][0] + e.w);
                    upd(dp[node][x + y][1], dp[node][x][1] + dp[e.to][y][1] + e.w * 2);
                }
            }
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    cin >> n >> k >> x;
    x--;

    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < K; j++) {
            for (int k = 0; k < 2; k++) {
                dp[i][j][k] = INF;
            }
        }
    }

    dfs(x, 0, -1);

    cout << dp[x][k][0];
 
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 675 ms 784076 KB Output is correct
2 Correct 678 ms 784388 KB Output is correct
3 Correct 671 ms 784404 KB Output is correct
4 Correct 703 ms 784252 KB Output is correct
5 Correct 681 ms 784348 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 790 ms 784672 KB Output is correct
2 Correct 972 ms 784552 KB Output is correct
3 Correct 692 ms 784860 KB Output is correct
4 Correct 689 ms 784648 KB Output is correct
5 Correct 693 ms 784524 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 790 ms 784672 KB Output is correct
2 Correct 972 ms 784552 KB Output is correct
3 Correct 692 ms 784860 KB Output is correct
4 Correct 689 ms 784648 KB Output is correct
5 Correct 693 ms 784524 KB Output is correct
6 Correct 854 ms 784612 KB Output is correct
7 Correct 728 ms 784880 KB Output is correct
8 Correct 840 ms 784536 KB Output is correct
9 Correct 846 ms 784632 KB Output is correct
10 Correct 811 ms 784632 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 675 ms 784076 KB Output is correct
2 Correct 678 ms 784388 KB Output is correct
3 Correct 671 ms 784404 KB Output is correct
4 Correct 703 ms 784252 KB Output is correct
5 Correct 681 ms 784348 KB Output is correct
6 Correct 790 ms 784672 KB Output is correct
7 Correct 972 ms 784552 KB Output is correct
8 Correct 692 ms 784860 KB Output is correct
9 Correct 689 ms 784648 KB Output is correct
10 Correct 693 ms 784524 KB Output is correct
11 Correct 854 ms 784612 KB Output is correct
12 Correct 728 ms 784880 KB Output is correct
13 Correct 840 ms 784536 KB Output is correct
14 Correct 846 ms 784632 KB Output is correct
15 Correct 811 ms 784632 KB Output is correct
16 Execution timed out 3067 ms 784704 KB Time limit exceeded
17 Halted 0 ms 0 KB -