Submission #645916

#	Time	Username	Problem	Language	Result	Execution time	Memory
645916		TimDee	Paths (RMI21_paths)	C++17	36 / 100	1096 ms	9316 KiB

Main

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

//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")

#define int long long
#define forn(i,n) for (int i=0; i<n; ++i)
#define pi pair<int,int>
#define pb(x) push_back(x)
#define f first
#define s second

vector<vector<pi>> adj(1e5+1);
int n,k;
vector<int> d;
vector<int> par;
int R;
unordered_map<int,unordered_map<int,int>> m;

void dfs(int u, int p) {
	for (auto x:adj[u]) {
		int v=x.f;
		if (v==p) continue;
		par[v]=u;
		d[v]=d[u]+x.s;
		dfs(v,u);
	}
}

void setd(int u) {
	for (auto x:adj[u]) {
		int v=x.f;
		if (v==par[u]) continue;
		d[v]=d[u]+x.s;
		setd(v);
	}
}

void climb(int u) {
	if (u==R) return;
	if (m[par[u]][u]) return;
	m[par[u]][u]=1;
	d[u]=0;
	for (auto x:adj[u]) {
		int v=x.f;
		if (v==par[u]) continue;
		if (m[u][v]) continue;
		d[v]=d[u]+x.s;
		setd(v);
	}
	climb(par[u]);
}

void root(int u) {
	R=u;
	d.assign(n+1,0);
	par.assign(n+1,0);
	m.clear();
	int ans=0;
	dfs(u,0);
	forn(i,k) {
		int mx=R;
		forn(j,n) {
			if (d[j+1]>d[mx]) mx=j+1;
		}
		ans+=d[mx];
		if (d[mx]==0) break;
		climb(mx);
	}
	cout<<ans<<'\n';
}

void solve() {
	
	cin>>n>>k;

	forn(i,n-1) {
		int u,v,x; cin>>u>>v>>x;
		adj[u].push_back({v,x});
		adj[v].push_back({u,x});
	}

	forn(i,n) root(i+1);

}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	solve();
	return 0;
}

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