Submission #1213623

#TimeUsernameProblemLanguageResultExecution timeMemory
1213623Sir_Ahmed_ImranPaths (RMI21_paths)C++17
36 / 100
1096 ms92412 KiB
// 01001100 01001111 01010100 01000001 \\ // \\ // ╦ ╔═╗╔╦╗╔═╗ \\ // ║ ║ ║ ║ ╠═╣ \\ // ╩═╝╚═╝ ╩ ╩ ╩ \\ // \\ // 01001100 01001111 01010100 01000001 \\ #include <bits/stdc++.h> using namespace std; #define N 100001 #define K 101 #define nl '\n' #define ff first #define ss second #define add insert #define ll long long #define ld long double #define terminator main #define pll pair<ll,ll> #define append push_back #define pii pair<int,int> #define all(x) (x).begin(),(x).end() #define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) int n, k; int s[N]; ll ans[N]; int par[N]; ll dp[N][K]; vector<pll> a[N]; void dfs(int v, int u){ if(par[v] == u) return; s[v] = 1; par[v] = u; vector<ll> x; for(auto & [i, j] : a[v]){ if(i == u) continue; dfs(i, v); s[v] += s[i]; x.append(dp[i][1] + j); for(int l = 1; l < min(k, s[i]); l++) x.append(dp[i][l + 1] - dp[i][l]); } sort(all(x)); reverse(all(x)); for(int i = 0; i < min(k, s[v]); i++){ dp[v][i + 1] = dp[v][i]; if(x.size() > i) dp[v][i + 1] += x[i]; } } void get(int v, int u){ dfs(v, -1); ans[v] = dp[v][k]; for(auto & [i, j] : a[v]) if(i != u) get(i, v); } void solve(){ int v, u, w; cin >> n >> k; for(int i = 1; i < n; i++){ cin >> v >> u >> w; a[v].append({u, w}); a[u].append({v, w}); } get(1, 0); for(int r = 1; r <= n; r++) cout << ans[r] << nl; } int terminator(){ L0TA; solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...