Submission #871451

#	Time	Username	Problem	Language	Result	Execution time	Memory
871451		evenvalue	Race (IOI11_race)	C++17	100 / 100	338 ms	43976 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;

  struct Dist {
    int weight_dist;
    int edge_dist;
  };

  auto calc_dist = [&](const int root, const int parent, Dist d) -> vector<Dist> {
    vector<Dist> distances;
    function<void(int, int, Dist)> rec = [&](int x, int p, Dist d) {
      if (d.weight_dist > k) return;
      distances.push_back(d);
      for (const auto [y, w] : g[x]) {
        if (decomposed[y] or y == p) continue;
        rec(y, x, Dist{ d.weight_dist + w, d.edge_dist + 1});
      }
    };
    rec(root, parent, d);
    return distances;
  };

  vector<pair<int, int>> path(k + 1, {kInf, -1});

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

    for (const auto [y, w] : g[x]) {
      if (decomposed[y]) continue;
      vector<Dist> distances = calc_dist(y, x, Dist{w, 1});
      for (const auto d : distances) {
        if (0 <= d.weight_dist and d.weight_dist <= k and path[k - d.weight_dist].second == x) {
          ans = min(ans, path[k - d.weight_dist].first + d.edge_dist);
        }
      }
      for (const auto d : distances) {
        if (0 <= d.weight_dist and d.weight_dist <= k) {
          if (path[d.weight_dist].second != x or path[d.weight_dist].first >= d.edge_dist) {
            path[d.weight_dist].first = d.edge_dist;
            path[d.weight_dist].second = x;
          }
        }
      }
    }

    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