제출 #956884

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

Firefighting

#include <bits/stdc++.h>
#define int long long
using namespace std; 
int const mxN = 3e5+5;
int dis[mxN], lift[mxN][20], elem[mxN], n, k, reach[mxN];
vector<pair<int,int>> adj[mxN];
bool vis[mxN];
vector<pair<int,pair<int,int>>> v;
int up ( int steps , int e) {
  for(int i=0; i<=18; i++) 
     if(steps&(1<<i)) e = lift[e][i];
  return e;
}
 
int bring ( int i ) {
  for(int j=18; j>=0; j--) {
    if(dis[i]-dis[lift[i][j]]<=k) i = lift[i][j];
  }
  return i;
}
 
void dfs ( int i , int p, int m) { 
  dis[i] = m;
  lift[i][0] = p;
  for(int j=1; j<20; j++) lift[i][j] = lift[lift[i][j-1]][j-1];
  elem[i] = bring(i);
  v.push_back({-dis[elem[i]], {elem[i], i}});
  for(auto it:adj[i]) {
    if(it.first==p) continue;
    dfs(it.first,i, m+it.second);
  }
}

void do_work ( int i , int p, int d) {
  vis[i] = 1;
  for(auto it:adj[i]) {
    if(it.first==p) continue;
    if(d+it.second>k) continue;
    if(reach[it.first]<d+it.second) continue;
    reach[it.first] = d+it.second;
    do_work(it.first, i, d+it.second);
  }
}
signed main() {
  
   ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
   cin>>n>>k;
   for(int i=1; i<=n+1; i++) reach[i] = 1e18;
   for(int i = 0; i<n-1; i++) {
    int x,y,c; cin>>x>>y>>c;
    adj[x].push_back({y,c}), adj[y].push_back({x,c});
   }   
   dfs(1,1,0);
   
   vector<int> fin;
   sort(v.begin(),v.end());
   for(auto it:v) {
     if(!vis[it.second.second]) {
      vis[it.second.second] = 1;
      do_work(it.second.first, 0, 0);
      fin.push_back(it.second.first);
     }
   }

   cout<<fin.size()<<'\n';
   for(auto it:fin) cout<<it<<' ';

   return 0;
  
}

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