Submission #645586

#	Time	Username	Problem	Language	Result	Execution time	Memory
645586		Vanilla	Paths (RMI21_paths)	C++17	68 / 100	484 ms	27108 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
typedef pair <int64, int64> pii;
const int maxn = 2e3 + 2;
vector <pii> ad [maxn];
vector <pii> lv;
priority_queue <int64> rs [maxn];
int dad [maxn];
int leaves = 0;
const int64 maxn1 = 1e5 + 2;
vector <int> ad1 [maxn1];
map <pair <int, int>, int64> cost1;
int64 dp [maxn1];
void dfs1 (int u, int p) {
    // cerr << u << " ";
    for (int v: ad1[u]) {
        if (v == p) continue;
        dfs1(v, u);
        dp[u] = max(dp[u], dp[v] + cost1[{u, v}]);
    }
}

void dfs2 (int u, int p, int64 sf) {
    dp[u] = max(dp[u], sf);
    vector <int> nd;
    for (int v: ad1[u]) {
        if (v == p) continue;
        nd.push_back(v);
    }
    int m = nd.size();
    vector <int64> pref(m), suff(m);
    if (m) {
        pref[0] = dp[nd[0]] + cost1[{u, nd[0]}];
        suff[m-1] = dp[nd[m-1]] + cost1[{u, nd[m-1]}];
        for (int i = 1; i < m; i++){
            pref[i] = max(pref[i-1], dp[nd[i]] + cost1[{u, nd[i]}]);
        }
        for (int i = m - 2; i >= 0; i--){
            suff[i] = max(suff[i + 1], dp[nd[i]] + cost1[{u, nd[i]}]);
        }
        for (int i = 0; i < m; i++){
            int64 p1 = (i ? pref[i-1]: 0);
            int64 p2 = ((i != m - 1) ? suff[i + 1]: 0);
            // cout << u << " " << nd[i] << " " << p1 << " " << p2 << " " << sf << " " << "\n";
            dfs2(nd[i], u, max({p1, p2, sf}) + cost1[{u, nd[i]}]);
        }
    }
}

void dfs (int u, int p) {
    while (!rs[u].empty()) rs[u].pop();
    for (auto [v, c]: ad[u]) {
        if (v == p) continue;
        dfs(v, u);
        int64 k = rs[v].top(); rs[v].pop();
        rs[v].push(k + c);
        if (rs[u].size() < rs[v].size()) swap(rs[u], rs[v]);
        while (!rs[v].empty()) {
            rs[u].push(rs[v].top());
            rs[v].pop();
        }
    }
    if (rs[u].empty()) rs[u].push(0);
    // cout << "> " << u << " " << rs[u].top() << "\n";
}

int main() {
    int n,k;
    cin >> n >> k;
    if (k == 1) {
        for (int i = 0; i < n - 1; i++){
            int a,b,c;
            cin >> a >> b >> c;
            ad1[a].push_back(b);
            ad1[b].push_back(a);
            cost1[{a,b}] = cost1[{b, a}] = c;
        }
        dfs1(1, -1);
        dfs2(1, -1, 0);
        for (int i = 1; i <= n; i++){
            // cout << i << ": ";
            cout << dp[i] << "\n";
        }
    }
    else {
        for (int i = 0; i < n - 1; i++){
            int a,b,c;
            cin >> a >> b >> c;
            ad[a].push_back({b, c});
            ad[b].push_back({a, c});
        }
        for (int i = 1; i <= n; i++){
            dfs(i, -1);
            int64 frs = 0;
            for (int j = 0; j < k && rs[i].size(); j++) {
                frs+=rs[i].top();
                rs[i].pop();
            }
            cout << frs << "\n";
        }
            
        
    }
}

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