Submission #645498

#	Time	Username	Problem	Language	Result	Execution time	Memory
645498		Vanilla	Paths (RMI21_paths)	C++17	19 / 100	1083 ms	5460 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
typedef pair <int64, int64> pii;
const int maxn = 1e3 + 2;
vector <int> ad [maxn];
vector <pii> lv;
int64 cost [maxn][maxn];
int dad [maxn];
int leaves = 0;

void prec (int u, int p, int64 sum) {
    bool f = 0;
    for (int v: ad[u]) {
        if (v == p) continue;
        f = 1;
        dad[v] = u;
        prec(v, u, sum + cost[u][v]);
    }
    if (!f) lv.push_back({sum, u});
}

int main() {
    int n,k;
    cin >> n >> k;
    for (int i = 0; i < n - 1; i++){
        int a,b,c;
        cin >> a >> b >> c;
        cost[a][b] = cost[b][a] = c;
        ad[a].push_back(b);
        ad[b].push_back(a);
    }
    for (int i = 1; i <= n; i++){
        if (ad[i].size() == 1) leaves++;
    }
    if (ad[1].size() == 1) leaves--;
    for (int i = 1; i <= n; i++){
        // k = min(k, leaves);
        int64 rs = 0;
        vector <pair <pii, int> > back;
        for (int j = 0; j < k; j++){
            lv.clear();
            prec(i, -1, 0);
            dad[i] = -1;
            sort(lv.rbegin(), lv.rend());
            // cout << i << " " << j << " " << lv[0].first << " " << lv[0].second << "\n";
            rs+=lv[0].first;
            int k = lv[0].second;
            while (k != i) {
                int p = dad[k];
                if (cost[p][k]) back.push_back({{p, k}, cost[p][k]});
                cost[p][k] = 0;
                k = p;
            }
        }
        for (auto [x, y]: back) {
            cost[x.first][x.second] = y;
        }
        // cout << i << ": ";
        cout << rs << "\n";
        
    }
}

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