Submission #901600

#	Time	Username	Problem	Language	Result	Execution time	Memory
901600		aminjonshermatov	Race (IOI11_race)	C++17	100 / 100	555 ms	47952 KiB

race

#include <bits/stdc++.h>

#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 42
#include "race.h"
#endif

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

  std::vector<int> size(n);
  std::vector<bool> died(n, false);
  auto dfs_sz = [&](auto& f, int v, int p) -> int {
    size[v] = 1;
    for (auto [u, _] : g[v]) {
      if (u != p && !died[u]) {
        size[v] += f(f, u, v);
      }
    }
    return size[v];
  };
  auto centroid = [&](auto& f, int v, int p, int desired) -> int {
    for (auto [u, _] : g[v]) {
      if (u != p && !died[u] && size[u] >= desired) {
        return f(f, u, v, desired);
      }
    }
    return v;
  };
  constexpr auto inf = std::numeric_limits<int>::max() / 2;
  std::vector<int> min_cnt(k + 1, inf);
  auto dfs_calc = [&](auto& f, int v, int p, int tot_w, int cnt, bool do_update, std::set<int>& touched) -> int {
    auto loc = inf;
    if (tot_w > k) {
      return loc;
    }
    if (do_update) {
      min_cnt[tot_w] = std::min(min_cnt[tot_w], cnt);
      touched.emplace(tot_w);
    } else {
      loc = std::min(loc, cnt + min_cnt[k - tot_w]);
    }
    for (auto [u, w] : g[v]) {
      if (u != p && !died[u]) {
        loc = std::min(loc, f(f, u, v, tot_w + w, cnt + 1, do_update, touched));
      }
    }
    return loc;
  };
  auto CD = [&](auto& f, int v, int p) -> int {
    auto c = centroid(centroid, v, p, dfs_sz(dfs_sz, v, p) / 2);
    died[c] = true;
    auto loc = inf;
    std::set<int> touched;
    for (auto [u, w] : g[c]) {
      if (!died[u]) {
        loc = std::min(loc, dfs_calc(dfs_calc, u, c, w, 1, false, touched));
        assert(dfs_calc(dfs_calc, u, c, w, 1, true, touched) == inf);
      }
    }
    for (auto w : touched) {
      min_cnt[w] = inf;
    }
    for (auto [u, _] : g[c]) {
      if (!died[u]) {
        loc = std::min(loc, f(f, u, c));
      }
    }
    return loc;
  };
  min_cnt[0] = 0;
  auto res = CD(CD, 0, -1);
  return res == inf ? -1 : res;
}

#ifdef LOCAL
void solve() {
  int n, k;
  std::cin >> n >> k;
  int H[n][2], L[n];
  for (int i = 0; i + 1 < n; ++i) {
    std::cin >> H[i][0] >> H[i][1] >> L[i];
  }
  std::cout << best_path(n, k, H, L) << '\n';
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  solve();
}
#endif

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