Submission #430546

#	Time	Username	Problem	Language	Result	Execution time	Memory
430546		Gurban	Race (IOI11_race)	C++17	0 / 100	62 ms	4172 KiB

race

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

using ll = long long;

const int maxn=1e6+5;
int ans,k;
int cnt[maxn];

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){
    cnt[ds] = min(cnt[ds],dis[lvl][nd]);
    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(int i = 0;i < maxn;i++) cnt[i] = 1e9;
    cnt[0] = 0;
    for(auto i : E[nd]) if(!done[i.first]) calc_dis(i.first,nd,lev[nd],i.second);
    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]);
  CD.calc(-1,0);
  return ans;
}

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


// }

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