Submission #1213610

#TimeUsernameProblemLanguageResultExecution timeMemory
1213610Ghulam_JunaidPaths (RMI21_paths)C++20
48 / 100
1096 ms10824 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 10; int n, k, mx, par[N], mark[N]; ll d[N], ans[N]; vector<pair<int, int>> g[N]; void dfs(int v, int p = 0){ if (d[v] > d[mx]) mx = v; for (auto [w, u] : g[v]){ if (u == p) continue; par[u] = v; d[u] = d[v] + w * (!mark[u]); dfs(u, v); } } int main(){ cin >> n >> k; for (int i = 0; i < n - 1; i ++){ int u, v, w; cin >> u >> v >> w; g[u].push_back({w, v}); g[v].push_back({w, u}); } if (k == 1){ dfs(1); int v = mx; d[v] = 0; dfs(v); for (int i = 1; i <= n; i ++) ans[i] = max(ans[i], d[i]); v = mx; d[v] = 0; dfs(v); for (int i = 1; i <= n; i ++) ans[i] = max(ans[i], d[i]); for (int i = 1; i <= n; i ++) cout << ans[i] << '\n'; return 0; } for (int v = 1; v <= n; v ++){ for (int i = 1; i <= n; i ++) mark[i] = 0; d[v] = 0; ll ans = 0; for (int i = 0; i < k; i ++){ mx = v; dfs(v); ans += d[mx]; int u = mx; while (!mark[u]){ mark[u] = 1; if (u == v) break; u = par[u]; } } cout << ans << '\n'; } }
#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...