oj.uz

Submission #161441

# Submission time Handle Problem Language Result Execution time Memory
161441 2019-11-02T15:16:22 Z Minnakhmetov Museum (CEOI17_museum) C++14
80 / 100
 3000 ms 9592 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 = 102, 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 10 ms 8568 KB Output is correct
2 Correct 10 ms 8568 KB Output is correct
3 Correct 11 ms 8588 KB Output is correct
4 Correct 11 ms 8568 KB Output is correct
5 Correct 10 ms 8568 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 9156 KB Output is correct
2 Correct 180 ms 9200 KB Output is correct
3 Correct 184 ms 9592 KB Output is correct
4 Correct 179 ms 9428 KB Output is correct
5 Correct 178 ms 9208 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 9156 KB Output is correct
2 Correct 180 ms 9200 KB Output is correct
3 Correct 184 ms 9592 KB Output is correct
4 Correct 179 ms 9428 KB Output is correct
5 Correct 178 ms 9208 KB Output is correct
6 Correct 178 ms 9128 KB Output is correct
7 Correct 182 ms 9368 KB Output is correct
8 Correct 178 ms 9088 KB Output is correct
9 Correct 178 ms 9080 KB Output is correct
10 Correct 175 ms 9080 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8568 KB Output is correct
2 Correct 10 ms 8568 KB Output is correct
3 Correct 11 ms 8588 KB Output is correct
4 Correct 11 ms 8568 KB Output is correct
5 Correct 10 ms 8568 KB Output is correct
6 Correct 181 ms 9156 KB Output is correct
7 Correct 180 ms 9200 KB Output is correct
8 Correct 184 ms 9592 KB Output is correct
9 Correct 179 ms 9428 KB Output is correct
10 Correct 178 ms 9208 KB Output is correct
11 Correct 178 ms 9128 KB Output is correct
12 Correct 182 ms 9368 KB Output is correct
13 Correct 178 ms 9088 KB Output is correct
14 Correct 178 ms 9080 KB Output is correct
15 Correct 175 ms 9080 KB Output is correct
16 Execution timed out 3051 ms 9056 KB Time limit exceeded
17 Halted 0 ms 0 KB -