Submission #1212439

#TimeUsernameProblemLanguageResultExecution timeMemory
1212439yanbPetrol stations (CEOI24_stations)C++20
18 / 100
3596 ms19156 KiB
#include <bits/stdc++.h> #define int long long using namespace std; using pii = pair<int, int>; int n, k; vector<vector<pii>> g; vector<int> order, a, ans; void dfs(int v, int p) { order.push_back(v); for (auto [u, uv] : g[v]) { if (u != p) { a.push_back(uv); dfs(u, v); } } } void solve(int root) { order.clear(); a.clear(); dfs(root, root); vector<int> pref(n); for (int i = 1; i < n; i++) { pref[i] = pref[i - 1] + a[i - 1]; } vector<int> z(n); for (int i = 0; i < n - 1; i++) { z[i] = lower_bound(pref.begin(), pref.end(), pref[i] + k + 1) - pref.begin() - 1; } vector<vector<int>> zT(n); for (int i = 0; i < n - 1; i++) { zT[z[i]].push_back(i); } vector<int> dp(n); for (int i = 0; i < n; i++) { dp[i] = 0; for (int p : zT[i]) { dp[i] += dp[p] + 1; } } for (int i = 0; i < n; i++) { ans[order[i]] += dp[i] * (n - i - 1); } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> k; g.resize(n); ans.resize(n); for (int i = 0; i < n - 1; i++) { int x, y, w; cin >> x >> y >> w; g[x].emplace_back(y, w); g[y].emplace_back(x, w); } int root = 0; for (int i = 0; i < n; i++) { if (g[i].size() == 1) { solve(i); } } for (int i = 0; i < n; i++) { cout << ans[i] << "\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...
#Verdict Execution timeMemoryGrader output
Fetching results...