Submission #647458

#	Time	Username	Problem	Language	Result	Execution time	Memory
647458		k_balint31415	Paths (RMI21_paths)	C++14	56 / 100	1072 ms	10952 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int c=1e5+5;


vector<pair<int,ll>> adj[c];
vector<ll> ut;

ll dfs(int v, int p, ll len){
    ll maxi=0;
    for(pair<int,ll> x: adj[v]){
        if(x.first != p){
            ll cur=dfs(x.first,v,x.second);
            if(cur>maxi){
                swap(cur,maxi);
            }
            ut.push_back(cur);
        }
    }
    return maxi+len;
}

int n,k;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n>>k;
    for(int i=1;i<n;i++){
        int a,b,val;
        cin>>a>>b>>val;
        adj[a].push_back(make_pair(b,val));
        adj[b].push_back(make_pair(a,val));
    }

    for(int i=1;i<=n;i++){
        ut.clear();
        ll ans=0;
        ut.push_back(dfs(i,0,0));
        sort(ut.rbegin(),ut.rend());
        for(int i=0;i<min(k,(int)ut.size());i++) ans+=ut[i];
        cout << ans << '\n'; 
    }
}

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