Submission #1154803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154803		AndrijaM	Arcade (NOI20_arcade)	C++20	0 / 100	515 ms	1114112 KiB

Arcade

#include<bits/stdc++.h>
using namespace std;

const int INF = 1e9, N = 1e4 + 5;
int dp[N][N][2], sz[N];
vector<pair<int, int>> g[N];

int getSize(int u, int p) {
    sz[u] = 1;
    for (auto &[v, _] : g[u]) if (v != p) sz[u] += getSize(v, u);
    return sz[u];
}

void dfs(int u, int p) {
    int total = 1;
    for (auto &[v, w] : g[u]) {
        if (v == p) continue;
        dfs(v, u);
        for (int i = total; i >= 0; i--) {
            for (int j = 0; j <= sz[v]; j++) {
                dp[u][i + j][0] = min({
                    dp[u][i + j][0],
                    dp[u][i][1] + dp[v][j][0] + w,
                    dp[u][i][0] + dp[v][j][1] + 2 * w
                });
                dp[u][i + j][1] = min(dp[u][i + j][1], dp[u][i][1] + dp[v][j][1] + 2 * w);
            }
        }
        total += sz[v];
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, k, x; cin >> n >> k >> x;

    fill(&dp[0][0][0], &dp[N-1][N-1][2] + 1, INF);
    
    for (int i = 1, u, v, w; i < n; i++) {
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }

    getSize(x, 0);
    dfs(x, 0);
    
    cout << dp[x][k][0] << "\n";
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 21
• Subtask 5: 0 / 14
• Subtask 6: 0 / 20
• Subtask 7: 0 / 15