Submission #430603

#	Time	Username	Problem	Language	Result	Execution time	Memory
430603		Gurban	Race (IOI11_race)	C++17	Compilation error	0 ms	0 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,int 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,int 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 < N;i++) cnt[i] = 1e9;
  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);
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cc1udTd7.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cchImC88.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status