Submission #959539

#TimeUsernameProblemLanguageResultExecution timeMemory
959539BlagojFirefighting (NOI20_firefighting)C++17
100 / 100
246 ms44172 KiB
#include <bits/stdc++.h> using namespace std; #define endl '\n' #define ll long long #define all(x) (x).begin(), (x).end() const int mxn = 3e5 + 10; ll n, k; vector<pair<ll, ll>> g[mxn]; vector<int> ans; pair<bool, ll> dfs(int cur, int par = -1, ll dist = 1e16) { ll mxOver = -1e16, mxUnder = 0; for (auto [to, weight] : g[cur]) { if (to == par) continue; auto res = dfs(to, cur, weight); if (res.first) mxOver = max(mxOver, res.second); else mxUnder = max(mxUnder, res.second); } pair<bool, ll> res; if (mxOver >= mxUnder) res = {1, mxOver - dist}; else res = {0, mxUnder + dist}; if (!res.first && res.second > k) { res = {1, k - dist}; ans.push_back(cur); } if (res.first && res.second < 0) res = {0, 0}; return res; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> k; for (int i = 0; i < n - 1; i++) { ll f, t, w; cin >> f >> t >> w; g[f].push_back({t, w}); g[t].push_back({f, w}); } dfs(1); cout << ans.size() << endl; for (auto x : ans) cout << x << " "; }
#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...