Submission #702713

#	Time	Username	Problem	Language	Result	Execution time	Memory
702713		TimDee	Paths (RMI21_paths)	C++17	0 / 100	1 ms	740 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<multiset<int>> ans(n);

vector<int> d(n,0);
vector<int> paiuans(n,0);
void paiu() {

}

void dfs(int u,int p) {
	for(auto&e:adj[u]) {
		int v=e.f,w=e.s;
		if (v==p) continue;
		dfs(v,u);
		int x=*ans[v].begin();
		ans[v].erase(ans[v].begin());
		ans[v].insert(x-w);
		if (ans[u].size()<ans[v].size()) swap(ans[u],ans[v]);
		for(auto&x:ans[v]) ans[u].insert(x);
	}
	//if (!ans[u].size()) 
		ans[u].insert(0);
}

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();
		dfs(u,-1);
		int answer=0;
		forn(i,k) {
			answer-=*ans[u].begin();
			ans[u].erase(ans[u].begin());
		}
		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: 0 / 8
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32