제출 #951299

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
951299		NourWael	Firefighting (NOI20_firefighting)	C++17	17 / 100	533 ms	25428 KiB

Firefighting

#include <bits/stdc++.h>
#define int long long
using namespace std; 
int const mxN = 3e5+5;
int n,k; 
vector<pair<int,int>> adj [mxN];
vector<int> put;
bool vis[mxN];

void dfs ( int i, int p, int d) {
   if(d>k) return;
   vis[i] = 1;
   for(auto it:adj[i]) {
      if(it.first==p) continue;
      dfs(it.first, i, d+it.second);
   }
}

vector<int> ans;

void check() {
   memset(vis,0,sizeof vis);
   for(auto it:put) dfs(it,0,0);
   for(int i=1; i<=n; i++) if(!vis[i]) return;
   if(ans.size()>put.size() || ans.empty()) ans = put;
}

void solve ( int i ) {
   if(i==n+1) { check(); return; }
   solve(i+1);
   put.push_back(i);
   solve(i+1);
   put.pop_back();
}

signed main() {
  
  ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
 
   cin>>n>>k;
   for(int i=0; i<n-1; i++) {
      int a,b,c; cin>>a>>b>>c;
      adj[a].push_back({b,c}), adj[b].push_back({a,c});
   }

   if(n<=17) {
      solve(1);
      cout<<ans.size()<<'\n';
      for(auto it:ans) cout<<it<<' ';
   }
   else {
      cout<<n<<'\n';
      for(int i=1; i<=n; i++) cout<<i<<' ';
   }
 
   return 0;
}

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