Submission #1172688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172688		Nurislam	Paths (RMI21_paths)	C++20	19 / 100	1095 ms	13384 KiB

Main

#include <bits/stdc++.h>

using namespace std;


#define int long long
#define pb push_back

int inf = 1e18; 

const int mod = 1e9 + 7;

//struct bitt {
	//vector<int> t;
	//int n;
	//bitt (int N) : n(N+1) {
		//t.resize(n+2);
	//};
	
	//void upd(int i, int va) { i ++ ;
		//for(; i < n; i += (i & -i)) t[i] += va;
	//};
	
	//int get(int i) { i ++ ;
		//int res = 0;
		//for(; i > 0; i -= (i & -i)) res += t[i];
		//return res;
	//};
	
	//int get(int l, int r) { r--;
		//return get(r ) - get( -- l );
	//};
//};

void solve(){
	int n, k;
	cin >> n >> k;
	
	vector<vector<array<int,2>>> g(n+1);
	for(int i = 1; i < n; i ++ ) {
		int a, b, c; cin >> a >> b >> c;
		g[a].push_back({b, c});
		g[b].push_back({a, c});
	};
	
	vector<vector<int> > dp(n+1, vector<int> (min(k+1, n+1), 0));
	
	function<void(int, int) > dfs = [&](int ps, int pr)  {
		
		for(auto [to, c] : g[ps]){
			if(to == pr)continue;
			
			dfs(to, ps);
			
			for(int j = dp[ps].size(); j >= 0; j -- ) {
				for(int i = 1; i+j < dp[ps].size(); i ++ ) {
					dp[ps][j+i] = max(dp[ps][j+i], dp[ps][j] + dp[to][i] + c);
				}
			}
		}
		
		//cout << ps << '\n';
		//for(int i = 0; i < dp[ps].size(); i ++ ) {
			//cout << dp[ps][i] << ' ';
		//}
		//cout << '\n';
	};
	
	//dfs(1, 1);
	
	
	for(int i = 1; i <= n; i ++ ) {
		dfs(i, i);
		cout << dp[i][k] << '\n';
		for(auto &i : dp)
			for(auto &j : i)j = 0;
	};
	
};

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	int tt = 1;
	//cin >> tt;
	
	while(tt -- ){
		solve();
	};
	
};

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