제출 #951299

#제출 시각아이디문제언어결과실행 시간메모리
951299NourWaelFirefighting (NOI20_firefighting)C++17
17 / 100
533 ms25428 KiB
#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;
}
#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...