Submission #1196677

#TimeUsernameProblemLanguageResultExecution timeMemory
1196677mmaitiPetrol stations (CEOI24_stations)C++20
18 / 100
3594 ms12480 KiB
#include <algorithm> #include <bits/stdc++.h> using namespace std; typedef long long ll; #define vi vector<int> #define si set<int> #define usi unordered_set<int> #define sll set<ll> #define usll unordered_set<ll> #define vb vector<bool> #define vll vector<ll> #define pii pair<int, int> #define pll pair<ll, ll> #define vvi vector<vector<int>> #define vvll vector<vector<ll>> ll N, K; vector<vector<pll>> AL; vll stops; vll stsz; ll fillSz(int num, int par) { stsz[num] = 1; for (auto i : AL[num]) { auto [nx, cost] = i; if (nx == par) continue; stsz[num] += fillSz(nx, num); } return stsz[num]; } void dfs(int num, int par, int fuel) { for (auto i : AL[num]) { auto [nx, cost] = i; if (nx == par) continue; if (fuel - cost < 0) { stops[num] += stsz[nx]; dfs(nx, num, K - cost); } else { dfs(nx, num, fuel - cost); } } } void solve() { cin >> N >> K; AL.resize(N); stops.resize(N); stsz.resize(N); ll a, b, w; for (int i = 0; i < N - 1; i++) { cin >> a >> b >> w; AL[a].push_back({b, w}); AL[b].push_back({a, w}); } for (int i = 0; i < N; i++) { fillSz(i, -1); dfs(i, -1, K); } for (int i = 0; i < N; i++) cout << stops[i] << "\n"; } int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); solve(); }
#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...