Submission #1172556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172556		versesrev	Race (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

// 23:47

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_size[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 function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:7:8: error: 'vector' is not a member of 'std'
    7 |   std::vector<std::vector<std::pair<int, long long>>> edges;
      |        ^~~~~~
race.cpp:1:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
  +++ |+#include <vector>
    1 | // 23:47
race.cpp:7:20: error: 'vector' is not a member of 'std'
    7 |   std::vector<std::vector<std::pair<int, long long>>> edges;
      |                    ^~~~~~
race.cpp:7:20: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
race.cpp:7:32: error: 'pair' is not a member of 'std'
    7 |   std::vector<std::vector<std::pair<int, long long>>> edges;
      |                                ^~~~
race.cpp:1:1: note: 'std::pair' is defined in header '<utility>'; did you forget to '#include <utility>'?
  +++ |+#include <utility>
    1 | // 23:47
race.cpp:7:37: error: expected primary-expression before 'int'
    7 |   std::vector<std::vector<std::pair<int, long long>>> edges;
      |                                     ^~~
race.cpp:8:25: error: expected unqualified-id before '-' token
    8 |   for (int i = 0; i < N.- 1; ++i) {
      |                         ^
race.cpp:9:5: error: 'edges' was not declared in this scope
    9 |     edges[H[i][0]].emplace_back(H[i][1], L[i]);
      |     ^~~~~
race.cpp:13:8: error: 'vector' is not a member of 'std'
   13 |   std::vector<bool> exist(N, true);
      |        ^~~~~~
race.cpp:13:8: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
race.cpp:13:15: error: expected primary-expression before 'bool'
   13 |   std::vector<bool> exist(N, true);
      |               ^~~~
race.cpp:14:8: error: 'vector' is not a member of 'std'
   14 |   std::vector<std::vector<int>> subtree_sizes;
      |        ^~~~~~
race.cpp:14:8: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
race.cpp:14:20: error: 'vector' is not a member of 'std'
   14 |   std::vector<std::vector<int>> subtree_sizes;
      |                    ^~~~~~
race.cpp:14:20: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
race.cpp:14:27: error: expected primary-expression before 'int'
   14 |   std::vector<std::vector<int>> subtree_sizes;
      |                           ^~~
race.cpp:15:8: error: 'vector' is not a member of 'std'
   15 |   std::vector<std::vector<int>> dists;
      |        ^~~~~~
race.cpp:15:8: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
race.cpp:15:20: error: 'vector' is not a member of 'std'
   15 |   std::vector<std::vector<int>> dists;
      |                    ^~~~~~
race.cpp:15:20: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
race.cpp:15:27: error: expected primary-expression before 'int'
   15 |   std::vector<std::vector<int>> dists;
      |                           ^~~
race.cpp:16:8: error: 'vector' is not a member of 'std'
   16 |   std::vector<std::vector<int>> depths;
      |        ^~~~~~
race.cpp:16:8: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
race.cpp:16:20: error: 'vector' is not a member of 'std'
   16 |   std::vector<std::vector<int>> depths;
      |                    ^~~~~~
race.cpp:16:20: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
race.cpp:16:27: error: expected primary-expression before 'int'
   16 |   std::vector<std::vector<int>> depths;
      |                           ^~~
race.cpp:17:8: error: 'vector' is not a member of 'std'
   17 |   std::vector<std::vector<int>> min_lengths;
      |        ^~~~~~
race.cpp:17:8: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
race.cpp:17:20: error: 'vector' is not a member of 'std'
   17 |   std::vector<std::vector<int>> min_lengths;
      |                    ^~~~~~
race.cpp:17:20: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
race.cpp:17:27: error: expected primary-expression before 'int'
   17 |   std::vector<std::vector<int>> min_lengths;
      |                           ^~~
race.cpp: In lambda function:
race.cpp:19:21: error: 'subtree_sizes' was not declared in this scope
   19 |     if (dc_depth >= subtree_sizes.size()) {
      |                     ^~~~~~~~~~~~~
race.cpp:21:7: error: 'dists' was not declared in this scope
   21 |       dists.emplace_back(N, 0);
      |       ^~~~~
race.cpp:22:7: error: 'depths' was not declared in this scope
   22 |       depths.emplace_back(N, 0);
      |       ^~~~~~
race.cpp:23:7: error: 'min_lengths' was not declared in this scope
   23 |       min_lengths.emplace_back(K + 1, N + 1);
      |       ^~~~~~~~~~~
race.cpp:26:18: error: 'invoke' is not a member of 'std'
   26 |     int g = std::invoke([&]{
      |                  ^~~~~~
race.cpp:1:1: note: 'std::invoke' is defined in header '<functional>'; did you forget to '#include <functional>'?
  +++ |+#include <functional>
    1 | // 23:47
race.cpp: In lambda function:
race.cpp:27:28: error: use of 'subtree_size' before deduction of 'auto'
   27 |       auto& subtree_size = subtree_size[dc_depth];
      |                            ^~~~~~~~~~~~
race.cpp:28:12: error: 'function' is not a member of 'std'
   28 |       std::function<int(int, int)> dfs = [&](int v, int p) {
      |            ^~~~~~~~
race.cpp:28:12: note: 'std::function' is defined in header '<functional>'; did you forget to '#include <functional>'?
race.cpp:28:33: error: expression list treated as compound expression in functional cast [-fpermissive]
   28 |       std::function<int(int, int)> dfs = [&](int v, int p) {
      |                                 ^
race.cpp:28:21: error: expected primary-expression before 'int'
   28 |       std::function<int(int, int)> dfs = [&](int v, int p) {
      |                     ^~~
race.cpp:37:7: error: 'dfs' was not declared in this scope
   37 |       dfs(root, -1);
      |       ^~~
race.cpp:43:28: error: 'edges' was not declared in this scope
   43 |         for (auto [u, _] : edges[g]) {
      |                            ^~~~~
race.cpp:44:19: error: 'exist' was not declared in this scope
   44 |           if (not exist[u] or u == last_g) continue;
      |                   ^~~~~
race.cpp:45:33: error: 'total' was not declared in this scope
   45 |           if (subtree_size[u] > total / 2) {
      |                                 ^~~~~
race.cpp: In lambda function:
race.cpp:55:5: error: 'exist' was not declared in this scope
   55 |     exist[g] = false;
      |     ^~~~~
race.cpp:57:24: error: 'edges' was not declared in this scope
   57 |     for (auto [u, _] : edges[g]) {
      |                        ^~~~~
race.cpp:58:7: error: use of 'dc' before deduction of 'auto'
   58 |       dc(dc_depth + 1, u);
      |       ^~
race.cpp:67:18: error: 'dists' was not declared in this scope; did you mean 'dist'?
   67 |     auto& dist = dists[dc_depth];
      |                  ^~~~~
      |                  dist
race.cpp:68:19: error: 'depths' was not declared in this scope; did you mean 'depth'?
   68 |     auto& depth = depths[dc_depth];
      |                   ^~~~~~
      |                   depth
race.cpp:69:24: error: 'min_lengths' was not declared in this scope; did you mean 'min_length'?
   69 |     auto& min_length = min_lengths[dc_depth];
      |                        ^~~~~~~~~~~
      |                        min_length
race.cpp:70:10: error: 'function' is not a member of 'std'
   70 |     std::function<void(int, int)> dfs = [&](int v, int p) {
      |          ^~~~~~~~
race.cpp:70:10: note: 'std::function' is defined in header '<functional>'; did you forget to '#include <functional>'?
race.cpp:70:32: error: expression list treated as compound expression in functional cast [-fpermissive]
   70 |     std::function<void(int, int)> dfs = [&](int v, int p) {
      |                                ^
race.cpp:70:19: error: expected primary-expression before 'void'
   70 |     std::function<void(int, int)> dfs = [&](int v, int p) {
      |                   ^~~~
race.cpp:88:5: error: 'dfs' was not declared in this scope
   88 |     dfs(g, -1);
      |     ^~~