Submission #315634

#	Time	Username	Problem	Language	Result	Execution time	Memory
315634		ivan_tudor	Race (IOI11_race)	C++14	0 / 100	4 ms	4992 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n,k;
int ANS;
struct muchii{
  int x;
  int d;
};
vector<muchii> gr[N];
int sz[N];
bool iscentr[N];
void dfs_sz(int nod,int dad){
  sz[nod] = 1;
  for(auto f:gr[nod]){
    if(f.x != dad && iscentr[f.x] == 0){
      dfs_sz(f.x,nod);
      sz[nod] += sz[f.x];
    }
  }
}
int findcentr(int nod,int dad, int bigroot){
  for(auto f:gr[nod]){
    if(f.x != dad && iscentr[f.x] == 0 && sz[f.x] > sz[bigroot]/2)
      return findcentr(f.x, nod, bigroot);
  }
  return nod;
}
void build_dfs(int nod,int dad,int distkm,int dst, map<int,int> &cur){
  if(distkm > k)
    return;
  if(cur.count(distkm))
    cur[distkm] = min(cur[distkm], dst);
  else
    cur[distkm] = dst;
  for(auto f:gr[nod]){
    if(f.x != dad && iscentr[f.x] == 0){
      build_dfs(f.x, nod, distkm + f.d, dst + 1, cur);
    }
  }
}
void buildcentr(int root){
  dfs_sz(root, 0);
  int cen = findcentr(root, 0, root);
  map<int,int> ansc;
  for(auto f:gr[cen]){
    if(iscentr[f.x] == 0){
      map<int,int> cur;
      build_dfs(f.x, cen, f.d, 1, cur);
      for(auto x:cur){
        if(ansc.count(k - x.first)){
          ANS = min(ANS, x.second +  ansc[k - x.first]);
        }
      }
      for(auto x:cur){
        if(ansc.count(x.first))
          ansc[x.first] = min(ansc[x.first], x.second);
        else
          ansc[x.first] = x.second;
      }
    }
  }
  iscentr[cen] = true;
  for(auto f: gr[cen]){
    if(iscentr[f.x] == 0)
      buildcentr(f.x);
  }
}
int best_path(int _n, int _k, int H[][2], int L[])
{
  k = _k;
  n = _n;
  for(int i=0;i<n-1;i++){
    int x, y;
    x = H[i][0] + 1;
    y = H[i][1] + 1;
    gr[x].push_back({y,L[i]});
    gr[y].push_back({x,L[i]});
  }
  ANS = INT_MAX;
  buildcentr(1);
  if(ANS == INT_MAX)
    return -1;
  return ANS;
}

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