Submission #1289242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289242		ykc0606	Paths (RMI21_paths)	C++20	56 / 100	1094 ms	11340 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long 
#define N 200001

using namespace std;
int n,k;
vector<pair<int,int>> adj[N];
int dis[N],leaf[N];
void dfs(int u,int p){
	if(adj[u].size()==1 && p!=-1){
		leaf[u]=u;
		dis[u]=0;
		return;
	}
	pair<int,int> mx={-1,-1};
	for(auto go:adj[u]){
		int v=go.fi;
		int w=go.se;
		if(v==p)continue;
		dfs(v,u);
		dis[leaf[v]]+=w;
		mx=max(mx,{dis[leaf[v]],leaf[v]});
	}
	dis[mx.se]=mx.fi;
	leaf[u]=mx.se;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> k;
	for(int i=1;i<n;i++){
		int x,y,c;
		cin >> x >> y >> c;
		adj[x].push_back({y,c});
		adj[y].push_back({x,c});
	}
	for(int i=1;i<=n;i++){
		dfs(i,-1);
		/*
		cout << i << " ";
		for(int j=1;j<=n;j++)cout << dis[j] << " ";
		cout << "\n";
		for(int j=1;j<=n;j++)cout << leaf[j] << " ";
		cout << "\n";
		*/
		vector<int> v;
		for(int j=1;j<=n;j++){
			if(leaf[j])v.push_back(dis[j]);
		} 
		sort(v.begin(),v.end());
		reverse(v.begin(),v.end());
		int ans=0;
		for(int i=0;i<k && i<(int)v.size();i++)ans+=v[i];
		cout << ans << "\n";
		for(int j=1;j<=n;j++){
			dis[j]=0;
			leaf[j]=0;
		}
	}
	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