Submission #537473

#TimeUsernameProblemLanguageResultExecution timeMemory
537473maomao90Paths (RMI21_paths)C++17
68 / 100
1057 ms63592 KiB
// Hallelujah, praise the one who set me free // Hallelujah, death has lost its grip on me // You have broken every chain, There's salvation in your name // Jesus Christ, my living hope #include <bits/stdc++.h> using namespace std; template <class T> inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;} template <class T> inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;} #define REP(i, s, e) for (int i = s; i < e; i++) #define RREP(i, s, e) for (int i = s; i >= e; i--) typedef long long ll; typedef long double ld; #define MP make_pair #define FI first #define SE second typedef pair<int, int> ii; typedef pair<ll, ll> pll; #define MT make_tuple typedef tuple<int, int, int> iii; #define ALL(_a) _a.begin(), _a.end() #define pb push_back typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ii> vii; #ifndef DEBUG #define cerr if (0) cerr #endif #define INF 1000000005 #define LINF 1000000000000000005ll #define MAXN 100005 int n, k; vii adj[MAXN]; priority_queue<ll> dp[MAXN]; void dfs(int u, int p) { while (!dp[u].empty()) { dp[u].pop(); } for (auto [v, w] : adj[u]) { if (v == p) continue; dfs(v, u); ll x = dp[v].top(); dp[v].pop(); dp[v].push(x + w); if (dp[u].size() < dp[v].size()) { swap(dp[u], dp[v]); } while (!dp[v].empty()) { ll x = dp[v].top(); dp[v].pop(); dp[u].push(x); } } if (dp[u].empty()) { dp[u].push(0); } } int main() { #ifndef DEBUG ios::sync_with_stdio(0), cin.tie(0); #endif cin >> n >> k; REP (i, 1, n) { int a, b, c; cin >> a >> b >> c; adj[a].pb(MP(b, c)); adj[b].pb(MP(a, c)); } if (k == 1) { vll dist(n + 1, 0); vll ans(n + 1, 0); auto dfs = [&] (auto &&self, int u, int p) { if (0) return -1; int mx = u; for (auto [v, w] : adj[u]) { if (v == p) continue; dist[v] = dist[u] + w; int x = self(self, v, u); if (dist[mx] < dist[x]) { mx = x; } } return mx; }; dist[1] = 0; int a = dfs(dfs, 1, -1); dist[a] = 0; int b = dfs(dfs, a, -1); REP (i, 1, n + 1) { mxto(ans[i], dist[i]); } dist[b] = 0; dfs(dfs, b, -1); REP (i, 1, n + 1) { mxto(ans[i], dist[i]); } REP (i, 1, n + 1) { cout << ans[i] << '\n'; } return 0; } REP (i, 1, n + 1) { dfs(i, -1); ll ans = 0; int tk = k; while (!dp[i].empty() && tk--) { ll x = dp[i].top(); dp[i].pop(); ans += x; } cout << ans << '\n'; } 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...