Submission #1076236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076236		TFF	Museum (CEOI17_museum)	C++17	0 / 100	15 ms	2908 KiB

museum

#include <bits/stdc++.h>
using namespace std;
int n, k, X;
vector<vector<int>> dp1[2];
vector<int> num;
vector<vector<pair<int, int>>> adj;

void solve2(int x, int p) {
    vector<vector<int>> dp2[2];
    for (auto v: adj[x]) {
        if (v.first == p) continue;
        solve2(v.first, x);
    }
    dp1[0][x].push_back(0);
    dp1[1][x].push_back(0);
    dp2[0].push_back({});
    dp2[1].push_back({});
    dp2[0][0].push_back(0);
    dp2[1][0].push_back(0);
    int s = 0;
    int cnt = 0;
    for (auto v: adj[x]) {
        if (v.first == p) continue;
        dp2[0].push_back({});
        dp2[1].push_back({});
        for (int i = 0; i <= min(s + num[v.first], k - 1); i++) {
            for (int j = max(0, i - num[v.first]); j <= min({s, k - 1, i}); j++) {
                if (j == max(0, i - num[v.first])) {
                    if (i != j) {
                        dp2[0].back().push_back(min(dp2[0][cnt][j] + dp1[1][v.first][i - j] + 2 * v.second, dp2[1][cnt][j] + dp1[0][v.first][i - j]) + v.second);
                        dp2[1].back().push_back(dp2[1][cnt][j] + dp1[1][v.first][i - j] + 2 * v.second);
                    } else {
                        dp2[0].back().push_back(dp2[0][cnt][j]);
                        dp2[1].back().push_back(dp2[1][cnt][j]);
                    }
                } else {
                    if (i != j) {
                        dp2[0][cnt + 1][i] = min(dp2[0][cnt + 1][i], min(dp2[0][cnt][j] + dp1[1][v.first][i - j] + 2 * v.second, dp2[1][cnt][j] + dp1[0][v.first][i - j] + v.second));
                        dp2[1][cnt + 1][i] = min(dp2[1][cnt + 1][i], dp2[1][cnt][j] + dp1[1][v.first][i - j] + 2 * v.second);
                    } else {
                        dp2[0][cnt + 1][i] = min(dp2[0][cnt + 1][i], dp2[0][cnt][j]);
                        dp2[1][cnt + 1][i] = min(dp2[1][cnt + 1][i], dp2[1][cnt][j]);
                    }
                }
            }
        }
        s += num[v.first];
        cnt++;
    }
    for (int i = 0; i < (int)dp2[0][cnt].size(); i++) {
        dp1[0][x].push_back(dp2[0][cnt][i]);
    }
    for (int i = 0; i < (int)dp2[1][cnt].size(); i++) {
        dp1[1][x].push_back(dp2[1][cnt][i]);
    }
}

int solve() {
    vector<vector<int>> dp2[2];
    for (auto v: adj[X]) {
        solve2(v.first, X);
    }
    dp2[0].push_back({});
    dp2[1].push_back({});
    dp2[0][0].push_back(0);
    dp2[1][0].push_back(0);
    int s = 0;
    int cnt = 0;
    for (auto v: adj[X]) {
        dp2[0].push_back({});
        dp2[1].push_back({});
        for (int i = 0; i <= min(s + num[v.first], k - 1); i++) {
            for (int j = max(0, i - num[v.first]); j <= min({s, k - 1, i}); j++) {
                if (j == max(0, i - num[v.first])) {
                    if (i != j) {
                        dp2[0].back().push_back(min(dp2[0][cnt][j] + dp1[1][v.first][i - j] + 2 * v.second, dp2[1][cnt][j] + dp1[0][v.first][i - j]) + v.second);
                        dp2[1].back().push_back(dp2[1][cnt][j] + dp1[1][v.first][i - j] + 2 * v.second);
                    } else {
                        dp2[0].back().push_back(dp2[0][cnt][j]);
                        dp2[1].back().push_back(dp2[1][cnt][j]);
                    }
                } else {
                    if (i != j) {
                        dp2[0][cnt + 1][i] = min(dp2[0][cnt + 1][i], min(dp2[0][cnt][j] + dp1[1][v.first][i - j] + 2 * v.second, dp2[1][cnt][j] + dp1[0][v.first][i - j] + v.second));
                        dp2[1][cnt + 1][i] = min(dp2[1][cnt + 1][i], dp2[1][cnt][j] + dp1[1][v.first][i - j] + 2 * v.second);
                    } else {
                        dp2[0][cnt + 1][i] = min(dp2[0][cnt + 1][i], dp2[0][cnt][j]);
                        dp2[1][cnt + 1][i] = min(dp2[1][cnt + 1][i], dp2[1][cnt][j]);
                    }
                }
            }
        }
        s += num[v.first];
        cnt++;
    }
    return dp2[0][cnt][k - 1];
}

void init(int x, int p = -1) {
    num[x] = 1;
    for (auto v: adj[x]) {
        if (v.first == p) continue;
        init(v.first, x);
        num[x] += num[v.first];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k >> X;
    adj.resize(n);
    dp1[0].resize(n);
    dp1[1].resize(n);
    num.resize(n);
    X--;
    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    init(X);
    cout << solve() << "\n";
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 25
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20