Submission #1289243

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289243		efeg	Paths (RMI21_paths)	C++20	56 / 100	1096 ms	8712 KiB

Main

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

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")


#define int long long
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define pb push_back
#define eb emplace_back
#define endl '\n'

typedef vector<int> vi;
typedef pair<long long,int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef tuple<int,int,int> iii;


int n,k,leafcnt; 
vector<vii> adj; 
vi dist; 

int dfs(int node,int p){
    int mxdist = 0,mxleaf = node;
    for (auto tp : adj[node]){
        int to,w; tie(to,w) = tp; 
        if (to == p) continue; 
        int leaf = dfs(to,node); 
        dist[leaf] += w; 
        
        if (adj[to].size() == 1) leafcnt++; 
        if (dist[leaf] > mxdist){
            mxleaf = leaf;
            mxdist = dist[leaf]; 
        }
    }
    return mxleaf; 
}
int32_t main(){
    ios_base::sync_with_stdio(NULL);cin.tie(NULL); cout.tie(NULL);  
    cin >> n >> k; 
    adj.assign(n + 10,vii()); 
    
    for (int i = 0; i < n-1; i++){
        int u,v,w; cin >> u >> v >> w; u--; v--; 
        adj[u].eb(v,w); 
        adj[v].eb(u,w); 
    }


    for (int root = 0; root < n; root++){
        leafcnt = 0; 
        dist.assign(n,0); 
        dfs(root,-1); 

        sort(all(dist),greater<int>());

        int ans = 0; 
        for (int i = 0; i < min(k,leafcnt); i++) ans += dist[i]; 
        cout << ans << endl; 

    }


    return 0; 

}

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