Submission #702719

#	Time	Username	Problem	Language	Result	Execution time	Memory
702719		TimDee	Paths (RMI21_paths)	C++17	56 / 100	222 ms	22164 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2,popcnt")

using ll = long long;
#define int long long
#define forn(i,n) for(int i=0; i<(n); ++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second
#define vii(a,n) vector<int> a(n); forn(i,n) cin>>a[i];
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int inf = INT_MAX;
const int mod = 998244353;

int n=2e3,k;
vector<vector<pi>> adj(n);
vector<vector<ll>> ans(n);
vector<int> mx(n,-1);

vector<int> d(n,0);
vector<int> paiuans(n,0);
void dfspaiu(int u, int p) {
	for(auto&e:adj[u]) {
		int v=e.f,w=e.s;
		if (v==p) continue;
		dfspaiu(v,u);
		d[u]=max(d[u],d[v]+w);
	}
}
void paia(int u, int p, int out) {
	vector<int> pref(1,0);
	paiuans[u]=max(d[u],out);
	for(auto&e:adj[u]) {
		int v=e.f,w=e.s;
		if (v==p) {pref.pb(pref.back()); continue;}
		pref.pb(max(pref.back(),d[v]+w));
	}
	int suf=0;
	int sz=adj[u].size();
	for(int i=sz-1; i>=0; --i) {
		auto e=adj[u][i];
		int v=e.f,w=e.s;
		if (v==p) continue;
		//cout<<v<<' '<<w<<"  "<<pref[i]<<' '<<suf<<'\n';
		paia(v,u,max({pref[i],suf,out})+w);
		suf=max(suf,d[v]+w);
	}
}
void paiu() {
	dfspaiu(0,-1);
	paia(0,-1,0);
	forn(i,n) cout<<paiuans[i]<<'\n';
	exit(0);
}

void dfs(int u,int p) {
	int m=-1;
	for(auto&e:adj[u]) {
		int v=e.f,w=e.s;
		if (v==p) continue;
		dfs(v,u);
		if (ans[u].size()<ans[v].size()) swap(ans[u],ans[v]);
		if (mx[v]+w>m) {
			if (m!=-1) ans[u].pb(m);
			m=mx[v]+w;
		} else {
			ans[u].pb(mx[v]+w);
		}
		for(auto&x:ans[v]) ans[u].pb(x);
	}
	mx[u]=max(m,0ll);
}

void solve() {

	cin>>n>>k;
	forn(i,n-1) {
		int u,v,w; cin>>u>>v>>w; --u, --v;
		adj[u].pb({v,w});
		adj[v].pb({u,w});
	}
	if (k==1) paiu();
	forn(u,n) {
		forn(i,n) ans[i].clear();
		mx.assign(n,-1);
		dfs(u,-1);
		ll answer=mx[u];
		sort(rall(ans[u]));

		forn(i,min(k-1,(int)ans[u].size())) {
			answer+=ans[u][i];
		}
		cout<<answer<<'\n';
	}

}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t=1;
    //cin>>t;
    while (t--) solve();
    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