Submission #333227

#TimeUsernameProblemLanguageResultExecution timeMemory
333227CantfindmeFirefighting (NOI20_firefighting)C++17
100 / 100
367 ms44892 KiB
#include <bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int> pi; #define f first #define s second #define FAST ios_base::sync_with_stdio(0); cin.tie(0); const int maxn = 300010; const int INF = LLONG_MAX/3; int n,k; vector <pi> adjlist[maxn]; vector <int> ans; int dfs(int x, int p, int d) { int maxover = -INF, minunder = 0; for (auto i: adjlist[x]) if (i.f != p) { int res = dfs(i.f,x,i.s); if (res < 0) minunder = min(minunder,res); else if (res > 0) maxover = max(maxover,res - i.s); } int res = 0; if (maxover < abs(minunder)) { if (abs(minunder) + d <= k) { //delay. Underflow res = -(abs(minunder) + d); } else { //Build here. overflow. ans.push_back(x); res = k; } } else if (maxover >= abs(minunder)) { res = maxover; } return res; } int32_t main() { FAST cin >> n >> k; for (int i =0;i<n-1;i++) { int a,b,d; cin >> a >> b >> d; adjlist[a].push_back(pi(b,d)); adjlist[b].push_back(pi(a,d)); } dfs(1,-1,INF); cout << ans.size() << "\n"; for (auto i: ans) cout << i << " "; }
#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...