Submission #645918

#	Time	Username	Problem	Language	Result	Execution time	Memory
645918		TimDee	Paths (RMI21_paths)	C++17	0 / 100	45 ms	19920 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;
bitset<2001> m[2001];
vector<int> leaves[2001];

void dfs(int u, int p) {
	if (adj[u].size()==1) {
		leaves[par[u]].pb(u);
	}
	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);
		for (auto x:leaves[v]) leaves[u].pb(x);
	}
}

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]].set(u);
	for (auto x:leaves[u]) d[x]-=d[u]-d[par[u]];
	d[u]=0;
	climb(par[u]);
}

void root(int u) {
	R=u;
	d.assign(n+1,0);
	par.assign(n+1,0);
	forn(i,2000) m[i+1].reset();
	forn(i,2000) leaves[i+1].clear();
	int ans=0;
	dfs(u,0);
	//cout<<"root "<<u<<'\n';
	forn(i,k) {
		int mx=leaves[R][0];
		for (auto v:leaves[R]) {
			if (d[v]>d[mx]) mx=v;
		}
		ans+=d[mx];
		climb(mx);
		//cout<<mx<<' '<<ans<<'\n';
	}
	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: 0 / 8
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32