Submission #116278

#	Time	Username	Problem	Language	Result	Execution time	Memory
116278		dragonslayerit	Race (IOI11_race)	C++14	100 / 100	769 ms	33260 KiB

race

#include "race.h"
#include <vector>
#include <map>
#include <stdint.h>

static const int INF=1e9+7;

static std::vector<std::pair<int,int> > adj[200005];
static int ans=INF;
static int size[200005];
static int KK;
static bool dead[200005];
static int best[1000005];

static int dfs_size(int node,int parent){
  size[node]=1;
  for(auto e:adj[node]){
    int child=e.first;
    if(dead[child]||child==parent) continue;
    dfs_size(child,node);
    size[node]+=size[child];
  }
}

static int find_centroid(int node,int parent,int total_size){
  for(auto e:adj[node]){
    int child=e.first;
    if(dead[child]||child==parent) continue;
    if(size[child]*2>total_size){
      return find_centroid(child,node,total_size);
    }
  }
  return node;
}

static void dfs_add(int node,int parent,int64_t dist,int len){
  if(dist>KK) return;
  best[dist]=std::min(best[dist],len);
  for(auto e:adj[node]){
    int child=e.first;
    if(dead[child]||child==parent) continue;
    dfs_add(child,node,dist+e.second,len+1);
  }
}

static void dfs_test(int node,int parent,int64_t dist,int len){
  if(dist>KK) return;
  ans=std::min(ans,best[KK-dist]+len);
  for(auto e:adj[node]){
    int child=e.first;
    if(dead[child]||child==parent) continue;
    dfs_test(child,node,dist+e.second,len+1);
  }
}

static void dfs_rem(int node,int parent,int64_t dist,int len){
  if(dist>KK) return;
  best[dist]=INF;
  for(auto e:adj[node]){
    int child=e.first;
    if(dead[child]||child==parent) continue;
    dfs_rem(child,node,dist+e.second,len+1);
  }
}

static void solve(int node){
  dfs_size(node,node);
  node=find_centroid(node,node,size[node]);
  best[0]=0;
  for(auto e:adj[node]){
    int child=e.first;
    if(dead[child]) continue;
    dfs_test(child,node,e.second,1);
    dfs_add(child,node,e.second,1);
  }
  for(auto e:adj[node]){
    int child=e.first;
    if(dead[child]) continue;
    dfs_rem(child,node,e.second,1);
  }
  dead[node]=true;
  for(auto e:adj[node]){
    int child=e.first;
    if(dead[child]) continue;
    solve(child);
  }
}

int best_path(int N, int K, int H[][2], int L[])
{
  for(int i=0;i<N;i++){
    adj[i].clear();
  }
  ans=INF;
  std::fill(dead,dead+N,false);
  KK=K;
  std::fill(best,best+1000001,INF);
  for(int i=0;i<N-1;i++){
    adj[H[i][0]].emplace_back(H[i][1],L[i]);
    adj[H[i][1]].emplace_back(H[i][0],L[i]);
  }
  solve(0);
  return ans<INF?ans:-1;
}

Compilation message (stderr)

race.cpp: In function 'int dfs_size(int, int)':
race.cpp:23:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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