제출 #871407

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
871407		evenvalue	Race (IOI11_race)	C++17	100 / 100	900 ms	50940 KiB

race

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

#ifdef evenvalue
  #include "debug.h"
#else
  #define debug(...)
#endif

template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;

using int64 = long long;
using ld = long double;

constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;

int best_path(const int n, const int k, int H[][2], int L[]) {
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < n - 1; i++) {
    const int x = H[i][0];
    const int y = H[i][1];
    const int w = L[i];
    g[x].emplace_back(y, w);
    g[y].emplace_back(x, w);
  }

  vector<int> sz(n);
  vector<bool> decomposed(n);

  function<int(int, int)> subtree_size = [&](const int x, const int p) {
    sz[x] = 1;
    for (const auto [y, w] : g[x]) {
      if (decomposed[y] or y == p) continue;
      sz[x] += subtree_size(y, x);
    }
    return sz[x];
  };

  function<int(int, int, int)> centroid = [&](const int x, const int p, const int size) {
    int c = x;
    for (const auto [y, w] : g[x]) {
      if (decomposed[y] or y == p) continue;
      if (2 * sz[y] < size) continue;
      c = centroid(y, x, size);
      break;
    }
    return c;
  };

  int ans = kInf;
  map<int64, int> path;

  function<void(int, int, int64, int)> upd_ans = [&](const int x, const int p, const int64 cost, const int d) {
    if (path.count(k - cost)) {
      ans = min(ans, path.at(k - cost) + d);
    }
    for (const auto [y, w] : g[x]) {
      if (decomposed[y] or y == p) continue;
      upd_ans(y, x, cost + w, d + 1);
    }
  };

  function<void(int, int, int64, int)> upd_path = [&](const int x, const int p, const int64 cost, const int d) {
    path.try_emplace(cost, d);
    path[cost] = min(path[cost], d);
    for (const auto [y, w] : g[x]) {
      if (decomposed[y] or y == p) continue;
      upd_path(y, x, cost + w, d + 1);
    }
  };

  function<void(int)> decompose = [&](int x) {
    x = centroid(x, -1, subtree_size(x, -1));
    decomposed[x] = true;

    path.clear();
    path[0] = 0;

    for (const auto [y, w] : g[x]) {
      if (decomposed[y]) continue;
      upd_ans(y, x, w, 1);
      upd_path(y, x, w, 1);
    }

    for (const auto [y, w] : g[x]) {
      if (decomposed[y]) continue;
      decompose(y);
    }
  };

  decompose(0);
  return (ans == kInf ? -1 : ans);
}

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