oj.uz

Submission #116271

# Submission time Handle Problem Language Result Execution time Memory
116271 2019-06-12T00:43:08 Z dragonslayerit Race (IOI11_race) C++14
0 / 100
 5 ms 5120 KB 
#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 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,std::map<int64_t,int>& best){
  if(best.count(dist)){
    best[dist]=std::min(best[dist],len);
  }else{
    best[dist]=len;
  }
  for(auto e:adj[node]){
    int child=e.first;
    if(dead[child]||child==parent) continue;
    dfs_add(child,node,e.second,len+1,best);
  }
}

static void dfs_test(int node,int parent,int64_t dist,int len,std::map<int64_t,int>& best){
  if(best.count(KK-dist)){
    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,e.second,len+1,best);
  }
}

static void solve(int node){
  dfs_size(node,node);
  node=find_centroid(node,node,size[node]);
  std::map<int64_t,int> best;
  best[0]=0;
  for(auto e:adj[node]){
    int child=e.first;
    dfs_add(child,node,e.second,1,best);
  }
  for(auto e:adj[node]){
    int child=e.first;
    if(dead[child]) continue;
    dfs_test(child,node,e.second,1,best);
  }
  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;
  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

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 5120 KB Output isn't correct
2 Halted 0 ms 0 KB -