oj.uz

Submission #161451

# Submission time Handle Problem Language Result Execution time Memory
161451 2019-11-02T15:25:58 Z Minnakhmetov Museum (CEOI17_museum) C++14
100 / 100
 939 ms 785264 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], sz[N];
int n, k, x;

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

void dive(int node, int anc) {
    sz[node] = 1;
    for (E e : g[node]) {
        if (e.to != anc) {
            dive(e.to, node);
            sz[node] += sz[e.to];
        }
    }
}

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

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

            for (int x = min(sum, k - h); x > 0; x--) {
                for (int y = 1; y <= min(sz[e.to], k - h - x); 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);
                }
            }
            sum += sz[e.to];
        }
    }
}

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;
            }
        }
    }

    dive(x, -1);
    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 677 ms 784268 KB Output is correct
2 Correct 761 ms 784308 KB Output is correct
3 Correct 669 ms 784120 KB Output is correct
4 Correct 775 ms 784084 KB Output is correct
5 Correct 681 ms 784276 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 692 ms 784632 KB Output is correct
2 Correct 764 ms 784764 KB Output is correct
3 Correct 690 ms 785120 KB Output is correct
4 Correct 753 ms 784936 KB Output is correct
5 Correct 690 ms 784732 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 692 ms 784632 KB Output is correct
2 Correct 764 ms 784764 KB Output is correct
3 Correct 690 ms 785120 KB Output is correct
4 Correct 753 ms 784936 KB Output is correct
5 Correct 690 ms 784732 KB Output is correct
6 Correct 699 ms 784632 KB Output is correct
7 Correct 704 ms 784992 KB Output is correct
8 Correct 689 ms 784748 KB Output is correct
9 Correct 701 ms 784760 KB Output is correct
10 Correct 721 ms 784760 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 677 ms 784268 KB Output is correct
2 Correct 761 ms 784308 KB Output is correct
3 Correct 669 ms 784120 KB Output is correct
4 Correct 775 ms 784084 KB Output is correct
5 Correct 681 ms 784276 KB Output is correct
6 Correct 692 ms 784632 KB Output is correct
7 Correct 764 ms 784764 KB Output is correct
8 Correct 690 ms 785120 KB Output is correct
9 Correct 753 ms 784936 KB Output is correct
10 Correct 690 ms 784732 KB Output is correct
11 Correct 699 ms 784632 KB Output is correct
12 Correct 704 ms 784992 KB Output is correct
13 Correct 689 ms 784748 KB Output is correct
14 Correct 701 ms 784760 KB Output is correct
15 Correct 721 ms 784760 KB Output is correct
16 Correct 764 ms 784604 KB Output is correct
17 Correct 815 ms 784888 KB Output is correct
18 Correct 720 ms 784888 KB Output is correct
19 Correct 740 ms 784772 KB Output is correct
20 Correct 726 ms 784888 KB Output is correct
21 Correct 867 ms 785108 KB Output is correct
22 Correct 837 ms 784772 KB Output is correct
23 Correct 939 ms 784888 KB Output is correct
24 Correct 878 ms 784760 KB Output is correct
25 Correct 850 ms 785264 KB Output is correct