Submission #1314656

#TimeUsernameProblemLanguageResultExecution timeMemory
1314656joshjuiceFirefighting (NOI20_firefighting)C++20
100 / 100
128 ms33612 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef pair<int, int> pii; #define pb push_back #define eb emplace_back #define fr first #define sc second #define sz(a) a.size() #define rep(x, a, b) for(auto x=a;(a<b?x<b:x>b);(a<b?x++:x--)) #define mnto(x,y) x = min(x, (__typeof__(x))y) #define mxto(x,y) x = max(x, (__typeof__(x))y) int n; ll k; vi ans; vector<pii> adj[300005]; pair<bool, ll> dfs(int idx, int p, ll d) { // mo is max distance from station child // mu is max distance from no-station child ll mo = LLONG_MIN, mu = 0; for (pii &pr : adj[idx]) { if (pr.fr != p) { pair<bool, ll> res = dfs(pr.fr, idx, pr.sc); if (res.fr) mxto(mo, res.sc); else mxto(mu, res.sc); } } pair<bool, ll> si; if (mo >= mu) si = {1, mo-d}; else si = {0, mu+d}; if (!si.fr && si.sc > k) { ans.pb(idx); si = {1, k-d}; } if (si.fr && si.sc < 0) si = {0, 0}; return si; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k; rep(i, 1, n) { int a, b, w; cin >> a >> b >> w; a--; b--; adj[a].eb(b, w); adj[b].eb(a, w); } dfs(0, -1, LLONG_MAX/4); cout << sz(ans) << '\n'; rep(i, 0, sz(ans)) cout << ans[i]+1 << ' '; }
#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...