Submission #1163292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163292		HappyCapybara	Race (IOI11_race)	C++20	100 / 100	898 ms	109308 KiB

race

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

int k;
int res = pow(10, 9);
vector<vector<pair<int,int>>> g;
vector<bool> cut;
vector<int> s;
vector<unordered_map<int,int>> d;

void dfs(int cur, int p){
  s[cur] = 1;
  for (auto [next, l] : g[cur]){
    if (next == p || cut[next]) continue;
    dfs(next, cur);
    s[cur] += s[next];
  }
}

void dfs2(int cur, int p, int st, int dist, int ul){
  if (dist > k) return;
  if (dist == k) res = min(res, ul);
  if (d[st].find(dist) == d[st].end()) d[st][dist] = ul;
  else d[st][dist] = min(d[st][dist], ul);
  for (auto [next, l] : g[cur]){
    if (next == p || cut[next]) continue;
    dfs2(next, cur, st, dist+l, ul+1);
  }
}

int centroid(int cur){
  dfs(cur, cur);
  if (s[cur] <= 2) return cur;
  int lim = s[cur]/2;
  int par = cur;
  while (true){
    int bo = -1;
    for (auto [next, l] : g[cur]){
      if (next == par || cut[next]) continue;
      if (s[next] >= lim) bo = next;
    }
    if (bo == -1) break;
    par = cur;
    cur = bo;
  }
  return cur;
}

void solve(int cur){
  int x = centroid(cur);
  unordered_map<int,int> um;
  for (auto [next, l] : g[x]){
    if (cut[next]) continue;
    d[next].clear();
    dfs2(next, x, next, l, 1);
    if (!um.empty()){
      for (auto [dist, ul] : d[next]){
        if (um.find(k-dist) != um.end()) res = min(res, ul+um[k-dist]);
      }
    }
    for (auto [dist, ul] : d[next]){
      if (um.find(dist) == um.end()) um[dist] = ul;
      else um[dist] = min(um[dist], ul);
    }
  }
  cut[x] = true;
  for (auto [next, l] : g[x]){
    if (!cut[next]) solve(next);
  }
}

int best_path(int N, int K, int H[][2], int L[]){
  k = K;
  g.resize(N);
  for (int i=0; i<N-1; i++){
    g[H[i][0]].push_back({H[i][1], L[i]});
    g[H[i][1]].push_back({H[i][0], L[i]});
  }
  cut.resize(N, false);
  s.resize(N);
  d.resize(N);
  solve(0);
  if (res == pow(10, 9)) return -1;
  return res;
}

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