제출 #765861

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765861		NeroZein	경주 (Race) (IOI11_race)	C++17	100 / 100	2094 ms	139584 KiB

race

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

const int MXN = 200005;
const int MXD = 2000006;

int k; 
int sz[MXN];
int dep[MXN]; 
long long dis[MXN];
vector<int> vec[MXN];
map<long long, multiset<int>> haveDis;
vector<pair<int, int>> g[MXN]; 

int ans; 
int Dfs (int v, int p) {
  sz[v] = 1;
  for (auto [u, w] : g[v]) {
    if (u != p) {
      dis[u] = dis[v] + w;
      dep[u] = dep[v] + 1;
      sz[v] += Dfs(u, v); 
    }
  }
  return sz[v];
}

void Dfs2 (int v, int p, bool keep) {
  int big = -1;
  for (auto [u, w] : g[v]) {
    if (u != p && (big == -1 || sz[u] > sz[big])) {
      big = u; 
    }
  }
  for (auto [u, w] : g[v]) {
    if (u != p && u != big) {
      Dfs2(u, v, false); 
    }
  }
  if (big != -1) {
    Dfs2(big, v, true);
    swap(vec[v], vec[big]);  
  }
  vec[v].push_back(v);
  
  for (auto [u, w] : g[v]) {
    if (u == p || u == big) {
      continue; 
    }
    for (int ch : vec[u]) {
      long long needed = k - dis[ch] + 2 * dis[v]; 
      if (needed >= 0 && !haveDis[needed].empty()) {
        ans = min(ans, dep[ch] + *haveDis[needed].begin() - 2 * dep[v]); 
      }
    }
    for (int ch : vec[u]) {
      vec[v].push_back(ch); 
      haveDis[dis[ch]].insert(dep[ch]); 
    }
  }
  long long needed = k + dis[v]; 
  if (needed >= 0 && !haveDis[needed].empty()) {
    ans = min(ans, *haveDis[needed].begin() - dep[v]); 
  }
  if (!keep) {
    for (int u : vec[v]) {
      if (u != v) {
        haveDis[dis[u]].erase(haveDis[dis[u]].find(dep[u]));
      }
    }
  }
  else {
    haveDis[dis[v]].insert(dep[v]); 
  }
}

int best_path(int N, int K, int H[][2], int L[]) {
  k = K; 
  for (int i = 0; i < N - 1; ++i) {
    g[H[i][0]].emplace_back(H[i][1], L[i]); 
    g[H[i][1]].emplace_back(H[i][0], L[i]); 
  }
  ans = N + 1; 
  Dfs(0, 0); 
  Dfs2(0, 0, true); 
  return (ans == N + 1 ? -1 : ans); 
}

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