Submission #1213619

#TimeUsernameProblemLanguageResultExecution timeMemory
1213619Sir_Ahmed_ImranPaths (RMI21_paths)C++17
19 / 100
687 ms7948 KiB
// 01001100 01001111 01010100 01000001 \\ // \\ // ╦ ╔═╗╔╦╗╔═╗ \\ // ║ ║ ║ ║ ╠═╣ \\ // ╩═╝╚═╝ ╩ ╩ ╩ \\ // \\ // 01001100 01001111 01010100 01000001 \\ #include <bits/stdc++.h> using namespace std; #define N 2001 #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 par[N]; ll dp[N][N]; vector<pll> a[N]; void dfs(int v, int u){ if(par[v] == u) return; par[v] = u; vector<ll> x; for(auto & [i, j] : a[v]){ if(i == u) continue; dfs(i, v); x.append(dp[i][1] + j); for(int l = 1; l < k; l++) x.append(dp[i][l + 1] - dp[i][l]); } sort(all(x)); reverse(all(x)); for(int i = 0; i < k; i++){ dp[v][i + 1] = dp[v][i]; if(!x.empty()) dp[v][i + 1] += x[i]; } } 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}); } for(int r = 1; r <= n; r++){ dfs(r, -1); cout << dp[r][k] << 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...