Submission #682564

#TimeUsernameProblemLanguageResultExecution timeMemory
682564raysh07Firefighting (NOI20_firefighting)C++17
100 / 100
300 ms47456 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define INF (int)1e18 mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); const int maxn = 3e5 + 69; vector<pair<int, int>> adj[maxn]; bool type[maxn]; vector<int> ans; int n, k; int dfs(int c, int p, int len) { int ma = 0, mi = INF; for(auto n2 : adj[c]) { int n = n2.first; int d = n2.second; if(n==p) continue; int l = dfs(n, c, d); if(type[n]) mi = min(mi, l); else ma = max(ma, l); } if(mi + ma > k) { if(len == -1 || ma + len > k) { type[c] = true; ans.push_back(c); return len; } type[c] = false; return len + ma; } if(mi+len > k) { type[c] = false; return 0; } type[c] = true; return len + mi; } void Solve() { cin>>n>>k; for (int i=1; i<n; i++){ int a, b, c; cin>>a>>b>>c; adj[a-1].push_back({b-1, c}); adj[b-1].push_back({a-1, c}); } dfs(0, -1, -1); cout<<ans.size()<<"\n"; for (auto x: ans)cout<<x +1 <<" "; } int32_t main() { auto begin = std::chrono::high_resolution_clock::now(); ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; //cin >> t; for(int i = 1; i <= t; i++) { //cout << "Case #" << i << ": "; Solve(); } auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; return 0; }
#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...