제출 #256909

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
256909		islingr	경주 (Race) (IOI11_race)	C++17	0 / 100	3076 ms	384 KiB

race

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

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define eb(x...) emplace_back(x)

bool ckmin(auto &a, const auto &b) { return a > b ? a = b, 1 : 0; }

using ll = int64_t;

int best_path(int n, int k, int h[][2], int l[]) {
  vector<bool> dead(n);
  vector<int> mn(k + 1), sz(n);
  vector<vector<int>> g(n);

  rep(e, 0, n - 1) g[h[e][0]].eb(e), g[h[e][1]].eb(e);

  int ans = n;

  function<int(int)> centroid = [&](int root) {
    function<void(int, int)> init = [&](int u, int p) {
      sz[u] = 1;
      for (int e : g[u]) {
        int v = h[e][u != h[e][1]];
        if (v != p && !dead[v])
          init(v, u), sz[u] += sz[v];
      }
    };
    init(root, -1);
    function<int(int, int)> dfs = [&](int u, int p) {
      for (int e : g[u]) {
        int v = h[e][u != h[e][1]];
        if (v != p && !dead[v] && 2 * sz[v] > sz[root])
          return dfs(v, u);
      }
      return u;
    };
    return dfs(root, -1);
  };

  function<void(int)> solve = [&](int s) {
    int root = centroid(s);

    function<void(int, int, int)> clear = [&](int u, int p, int dist) {
      if (dist > k) return;
      mn[dist] = mn[k - dist] = n;
      for (int e : g[u]) {
        int v = h[u][e != h[u][1]];
        if (v != p && !dead[v])
          clear(v, u, dist + l[e]);
      }
    };
    clear(root, -1, 0);

    vector<pair<int, int>> lazy;
    int dep = 0;
    function<void(int, int, int)> dfs = [&](int u, int p, int dist) {
      if (dist > k) return;
      ckmin(ans, dep + mn[k - dist]);
      lazy.eb(dist, dep);
      ++dep;
      for (int e : g[u]) {
        int v = h[u][e != h[u][1]];
        if (v != p && !dead[v])
          dfs(v, u, dist + l[e]);
        if (u == root) {
          for (auto [dist, dep] : lazy)
            ckmin(mn[dist], dep);
          lazy.clear();
        }
      }
      --dep;
    };
    mn[0] = 0; dfs(root, -1, 0);

    dead[root] = true;
    for (int v : g[root]) if (!dead[v]) solve(v);
  };
  solve(0);
  
  return ans != n ? ans : -1;
}

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