Submission #1241654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241654		borisAngelov	Paths (RMI21_paths)	C++20	36 / 100	1094 ms	18384 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2005;

int n, k;
vector<pair<int, int>> g[maxn];
long long dp[maxn][maxn];
pair<long long, int> max1[maxn];

void dfs(int node, int par)
{
    for (int i = 0; i <= k; ++i)
    {
        dp[node][i] = 0;
    }

    vector<pair<int, int>> children;

    for (auto [to, w] : g[node])
    {
        if (to != par)
        {
            children.push_back({to, w});
            dfs(to, node);
        }
    }

    long long curr = 0;
    int cntNodes = 0;
    vector<long long> deltas;

    for (auto [v, w] : children)
    {
        curr += max1[v].first + w;
        cntNodes += max1[v].second;

        for (int i = max1[v].second; i >= 1; --i)
        {
            if (i > 1) deltas.push_back(dp[v][i] - dp[v][i - 1]);
            else deltas.push_back(dp[v][i] - dp[v][i - 1] + w);
            //cout << "added " << deltas.back() << endl;
        }
    }

    //cout << "now " << node << " " << curr << " :: " << cntNodes << endl;

    sort(deltas.begin(), deltas.end());
    int ptr = 0, last = -1;

    for (int i = cntNodes; i >= 1; --i)
    {
        if (i <= k) 
        {
            dp[node][i] = curr;
            //cout << "fill " << i << " :: " << curr << endl;
            if (last == -1) last = i;
        }
        curr -= deltas[ptr];
        ++ptr;
    }

    //cout << "here -> " << last << endl;
    for (int i = last + 1; i <= k; ++i)
    {
        dp[node][i] = dp[node][i - 1];
    }

    max1[node] = {dp[node][1], 1};
    for (int i = 2; i <= k; ++i)
    {
        if (max1[node].first < dp[node][i])
        {
            max1[node] = {dp[node][i], i};
        }
    }

    /*cout << "ON " << node << endl;
    for (int i = 0; i <= k; ++i) cout << dp[node][i] << " ";
    cout << endl;
    cout << "-> " << max1[node].first << " " << max1[node].second << endl;
    cout << "------------------------" << endl;*/
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> k;

    for (int i = 1; i < n; ++i)
    {
        int x, y, w;
        cin >> x >> y >> w;
        g[x].push_back({y, w});
        g[y].push_back({x, w});
    }

    for (int i = 1; i <= n; ++i)
    {
        dfs(i, -1);
        cout << dp[i][k] << "\n";
    }

    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32