oj.uz

Submission #161444

# Submission time Handle Problem Language Result Execution time Memory
161444 2019-11-02T15:18:17 Z Minnakhmetov Museum (CEOI17_museum) C++14
80 / 100
 3000 ms 785116 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 anc) {
    dp[node][1][0] = dp[node][1][1] = 0;

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

            for (int x = k; x > 0; x--) {
                for (int y = 1; x + y <= k; 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, -1);

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 747 ms 784464 KB Output is correct
2 Correct 721 ms 784120 KB Output is correct
3 Correct 744 ms 784176 KB Output is correct
4 Correct 746 ms 784276 KB Output is correct
5 Correct 733 ms 784328 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 861 ms 784868 KB Output is correct
2 Correct 869 ms 784864 KB Output is correct
3 Correct 871 ms 785116 KB Output is correct
4 Correct 850 ms 785016 KB Output is correct
5 Correct 847 ms 784680 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 861 ms 784868 KB Output is correct
2 Correct 869 ms 784864 KB Output is correct
3 Correct 871 ms 785116 KB Output is correct
4 Correct 850 ms 785016 KB Output is correct
5 Correct 847 ms 784680 KB Output is correct
6 Correct 947 ms 784648 KB Output is correct
7 Correct 868 ms 784888 KB Output is correct
8 Correct 868 ms 784664 KB Output is correct
9 Correct 848 ms 784784 KB Output is correct
10 Correct 836 ms 784804 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 747 ms 784464 KB Output is correct
2 Correct 721 ms 784120 KB Output is correct
3 Correct 744 ms 784176 KB Output is correct
4 Correct 746 ms 784276 KB Output is correct
5 Correct 733 ms 784328 KB Output is correct
6 Correct 861 ms 784868 KB Output is correct
7 Correct 869 ms 784864 KB Output is correct
8 Correct 871 ms 785116 KB Output is correct
9 Correct 850 ms 785016 KB Output is correct
10 Correct 847 ms 784680 KB Output is correct
11 Correct 947 ms 784648 KB Output is correct
12 Correct 868 ms 784888 KB Output is correct
13 Correct 868 ms 784664 KB Output is correct
14 Correct 848 ms 784784 KB Output is correct
15 Correct 836 ms 784804 KB Output is correct
16 Execution timed out 3102 ms 784656 KB Time limit exceeded
17 Halted 0 ms 0 KB -