제출 #1172603

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172603		versesrev	경주 (Race) (IOI11_race)	C++20	100 / 100	621 ms	73920 KiB

race

// 23:47

#include <vector>
#include <utility>
#include <functional>

int best_path(int N, int K, int H[][2], int L[]) {
  if (N == 1) {
    return -1;
  }
  std::vector<std::vector<std::pair<int, int>>> edges(N, std::vector<std::pair<int, int>>());
  for (int i = 0; i < N - 1; ++i) {
    edges[H[i][0]].emplace_back(H[i][1], L[i]);
    edges[H[i][1]].emplace_back(H[i][0], L[i]);
  }
  int ans = N + 1;
  std::vector<bool> exist(N, true);
  std::vector<std::vector<int>> subtree_sizes;
  std::vector<std::vector<int>> dists;
  std::vector<std::vector<int>> depths;
  auto dc = [&](auto&& self, int dc_depth, int root) -> void {
    if (dc_depth >= subtree_sizes.size()) {
      subtree_sizes.emplace_back(N, 0);
      dists.emplace_back(N, 0);
      depths.emplace_back(N, 0);
    }
    // find centroid
    int g = std::invoke([&]{
      auto& subtree_size = subtree_sizes[dc_depth];
      auto compute_size = [&](auto&& self, int v, int p) -> int {
        subtree_size[v] = 1;
        for (auto [u, _] : edges[v]) {
          if (not exist[u] or u == p) continue;
          subtree_size[v] += self(self, u, v);
        }
        return subtree_size[v];
      };
      compute_size(compute_size, root, -1);
      const int total_size = subtree_size[root];
      auto get_centroid = [&](auto&& self, int v, int p) -> int {
        for (auto [u, _] : edges[v]) {
          if (not exist[u] or u == p) continue;
          if (subtree_size[u] > total_size / 2) return self(self, u, v);
        }
        return v;
      };
      return get_centroid(get_centroid, root, -1);
    });
    exist[g] = false;
    // dc(subtrees)
    for (auto [u, _] : edges[g]) {
      if (not exist[u]) continue;
      self(self, dc_depth + 1, u);
    }
    //exist[g] = true; return;
    // merge
    //   dfs to get dist
    //.  for each subtree
    //.    for each node
    //.      try to update ans d[node]
    //.    for each node
    //.      update query map
    auto& dist = dists[dc_depth];
    auto& depth = depths[dc_depth];
    std::vector<int> nodes;
    auto dfs = [&](auto&& self, int v, int p) -> void {
      if (dist[v] > K) return;
      nodes.push_back(v);
      for (auto [u, w] : edges[v]) {
        if (not exist[u] or u == p) continue;
        dist[u] = dist[v] + w;
        depth[u] = depth[v] + 1;
        self(self, u, v);
      }
    };
    std::unordered_map<int, int> min_length;
    dist[g] = 0;
    depth[g] = 0;
    min_length[0] = 0;
    for (auto [u, w] : edges[g]) {
      if (not exist[u]) continue;
      dist[u] = w;
      depth[u] = 1;
      nodes.clear();
      dfs(dfs, u, g);
      for (int v : nodes) {
        auto it = min_length.find(K - dist[v]);
        if (it != min_length.end()) {
          ans = std::min(ans, depth[v] + it->second);
        }
      }
      for (int v : nodes) {
        auto it = min_length.find(dist[v]);
        if (it == min_length.end() or depth[v] < it->second) {
          min_length[dist[v]] = depth[v];
        }
      }
    }
    exist[g] = true;
  };
  dc(dc, 0, 0);
  return ans == N + 1 ? -1 : ans;
}

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