Submission #1172558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172558		versesrev	Race (IOI11_race)	C++20	Compilation error	0 ms	0 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, long long>>> edges;
  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;
  std::vector<std::vector<int>> min_lengths;
  auto dc = [&](int dc_depth, int root) {
    if (dc_depth >= subtree_sizes.size()) {
      subtree_sizes.emplace_back(N, 0);
      dists.emplace_back(N, 0);
      depths.emplace_back(N, 0);
      min_lengths.emplace_back(K + 1, N + 1);
    }
    // find centroid
    int g = std::invoke([&]{
      auto& subtree_size = subtree_sizes[dc_depth];
      std::function<int(int, int)> dfs = [&](int v, int p) {
        subtree_size[v] = 1;
        for (auto [u, _] : edges[v]) {
          if (not exist[u] or u == p) continue;
          int u_size = dfs(u, v);
          subtree_size[v] += u;
        }
        return subtree_size[v];
      };
      dfs(root, -1);
      int total_size = subtree_size[root];
      int g = root;
      int last_g = -1;
      while (true) {
        bool is_centroid = true;
        for (auto [u, _] : edges[g]) {
          if (not exist[u] or u == last_g) continue;
          if (subtree_size[u] > total / 2) {
            is_centroid = false;
            last_g = g;
            g = u;
          }
        }
        if (is_centroid) break;
      }
      return g;
    });
    exist[g] = false;
    // dc(subtrees)
    for (auto [u, _] : edges[g]) {
      dc(dc_depth + 1, u);
    }
    // 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];
    auto& min_length = min_lengths[dc_depth];
    std::function<void(int, int)> dfs = [&](int v, int p) {
      if (dist[v] > K) return;
      if (dist[v] == K) {
        ans = std::min(ans, depth[v]);
      }
      else if (dist[v] < K) {
        ans = std::min(ans, depth[v] + min_length[K - dist[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;
        dfs(u, v);
      }
      min_length[dist[v]] = std::min(min_length[dist[v]], depth[v]);
    };
    dist[g] = 0;
    depth[g] = 0;
    dfs(g, -1);
  };
  dc(0, 0);
  return ans == N + 1 ? -1 : ans;
}

Compilation message (stderr)

race.cpp: In lambda function:
race.cpp:49:33: error: 'total' was not declared in this scope
   49 |           if (subtree_size[u] > total / 2) {
      |                                 ^~~~~
race.cpp: In lambda function:
race.cpp:62:7: error: use of 'dc' before deduction of 'auto'
   62 |       dc(dc_depth + 1, u);
      |       ^~