Submission #1212464

#TimeUsernameProblemLanguageResultExecution timeMemory
1212464yanbPetrol stations (CEOI24_stations)C++20
38 / 100
3595 ms34632 KiB
#include <bits/stdc++.h> #define int long long using namespace std; using pii = pair<int, int>; using t3i = tuple<int, int, int>; int n, k; vector<vector<t3i>> g; vector<t3i> e; vector<int> ans, R, sz, vsz; vector<vector<int>> F; vector<bool> uF; void dfs_R(int ei) { if (uF[ei]) return; uF[ei] = 1; auto [from, to, w] = e[ei]; F[ei][k - w] += 1; for (auto [u, _, eu] : g[from]) { if (u != to) { dfs_R(eu ^ 1); for (int i = 0; i <= k; i++) { if (i >= w) { F[ei][i - w] += F[eu ^ 1][i]; } else { F[ei][k - w] += F[eu ^ 1][i]; R[ei] += F[eu ^ 1][i]; } } } } } void dfs_sz(int v, int p) { vsz[v] = 1; for (auto [u, _1, _2] : g[v]) { if (u != p) { dfs_sz(u, v); vsz[v] += vsz[u]; } } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> k; g.resize(n); ans.resize(n); e.resize(2 * n - 2); for (int i = 0; i < n - 1; i++) { int x, y, w; cin >> x >> y >> w; g[x].emplace_back(y, w, i * 2); g[y].emplace_back(x, w, i * 2 + 1); e[i * 2] = {x, y, w}; e[i * 2 + 1] = {y, x, w}; } vsz.resize(n); sz.resize(2 * n - 2); dfs_sz(0, 0); for (int i = 0; i < 2 * n - 2; i++) { auto [u, v, _] = e[i]; if (vsz[u] > vsz[v]) { sz[i] = vsz[v]; } else { sz[i] = n - vsz[u]; } } F.resize(2 * n - 2, vector<int>(k + 1)); uF.resize(2 * n - 2); R.resize(2 * n - 2); for (int i = 0; i < 2 * n - 2; i++) { dfs_R(i); } for (int v = 0; v < n; v++) { for (auto [_1, _2, ei] : g[v]) { ans[v] += R[ei] * sz[ei]; } } 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...