Submission #1193441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193441		loom	Firefighting (NOI20_firefighting)	C++20	100 / 100	134 ms	39108 KiB

Firefighting

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define nl '\n'

const int N = 3e5+1;
int k;
vector<pair<int,int>> g[N];
vector<int> ans;

pair<int,int> dfs(int v, int p, int d){
   int mx_ov = -1, mx_un = 0;
   
   for(auto [ch, w] : g[v]){
      if(ch == p) continue;

      auto [tf, x] = dfs(ch, v, w);
      
      if(tf) mx_ov = max(mx_ov, x);
      else mx_un = max(mx_un, x);
   }

   if(mx_ov >= mx_un){
      if(mx_ov >= d) return {1, mx_ov - d};
      else return {0, 0}; 
   }else{
      if(mx_un + d <= k) return {0, mx_un + d};
      else{
         ans.push_back(v);
         if(k >= d) return {1, k-d};
         else return {0, 0};
      }
   }
}

inline void solve(){
   int n;
   cin>>n>>k;
   for(int i=1; i<n; i++){
      int a, b, w;
      cin>>a>>b>>w;
      g[a].push_back({b, w});
      g[b].push_back({a, w});
   }

   if(dfs(1, 0, 0).first == 0) ans.push_back(1);
   cout<<ans.size()<<nl;
   for(int x : ans) cout<<x<<" ";
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 5 / 5
• Subtask 3: 9 / 9
• Subtask 4: 19 / 19
• Subtask 5: 26 / 26
• Subtask 6: 38 / 38