제출 #430615

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
430615		Gurban	경주 (Race) (IOI11_race)	C++17	9 / 100	220 ms	38872 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;

using ll = long long;

const int maxn=1e6+5;
int ans = 1e9,k;
int cnt[maxn];
vector<int>v;

struct Centroid {
  int N;
  vector<vector<pair<int,int>>>E;
  vector<bool>done;
  vector<int>sub,pc,lev;
  vector<vector<int>>dis;
  void add_edge(int x,int y,int w){
    E[x].push_back({y,w});
    E[y].push_back({x,w});
  }
  void init(int _N){
    N = _N;
    E.resize(N);
    done.resize(N);
    sub.resize(N),pc.resize(N),lev.resize(N);
    dis.resize(32-__builtin_clz(N));
    for(int i = 0;i < (int)dis.size();i++) dis[i].resize(N);
  }
  void dfs(int nd,int pr){
    for(auto i : E[nd]){
      sub[i.first] = 1;
      if(i.first != pr and !done[i.first]) dfs(i.first,nd), sub[nd] += sub[i.first];
    }
  }
  int centroid(int nd){
    dfs(nd,-1);
    int sz = sub[nd];
    while(1){
      pair<int,int>mx = {0,0};
      for(auto i : E[nd]) if(!done[i.first] and sub[i.first] < sub[nd])
        if(sub[i.first] > mx.first) mx = {sub[i.first],i.first};
      if(mx.first*2 <= sz) return nd;
      nd = mx.second;
    }
  }
  void calc_dis(int nd,int pr,int lvl,ll ds){
    dis[lvl][nd] = dis[lvl][pr] + 1;
    if(ds <= k) ans = min(ans,cnt[k-ds]+dis[lvl][nd]);
    for(auto i : E[nd]) if(i.first != pr and !done[i.first]) calc_dis(i.first,nd,lvl,ds+i.second);
  }
  void put(int nd,int pr,int lvl,ll ds){
    if(ds < maxn and cnt[ds] > dis[lvl][nd]){
      cnt[ds] = dis[lvl][nd];
      v.push_back(ds);
    }
    for(auto i : E[nd]) if(i.first != pr and !done[i.first]) put(i.first,nd,lvl,ds+i.second);
  }
  void calc(int PC,int _nd){
    int nd = centroid(_nd); done[nd] = 1,pc[nd] = PC;
    sub[nd] = sub[_nd]; lev[nd] = (PC == -1 ? 0 : lev[PC] + 1);
    dis[lev[nd]][nd] = 0;
    for(auto i : E[nd]) if(!done[i.first]){
      calc_dis(i.first,nd,lev[nd],i.second);
      put(i.first,nd,lev[nd],i.second);  
    }
    for(auto i : v) cnt[i] = 1e9;
    v.clear();
    for(auto i : E[nd]) if(!done[i.first]) calc(nd,i.first);
  }
};

int best_path(int N, int K, int H[][2], int L[]){   
  k = K;
  Centroid CD;
  CD.init(N);
  for(int i = 0;i < N-1;i++) CD.add_edge(H[i][0],H[i][1],L[i]);
  for(int i = 1;i < maxn;i++) cnt[i] = 1e9;
  cnt[0] = 0;
  CD.calc(-1,0);
  if(ans == 1e9) ans = -1;
  return ans;
}

// int main(){
//   ios::sync_with_stdio(false);
//   cin.tie(0);

//   int n,k; cin >> n >> k;
//   int H[n][2],L[n];
//   for(int i = 0;i < n-1;i++){
//     int x,y,w; cin >> x >> y >> w;
//     H[i][0] = x,H[i][1] = y;
//     L[i] = w;
//   }
//   cout<<best_path(n,k,H,L);
// }

• Subtask 1: 9 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57