Submission #1108191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108191		keunbum	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>

using namespace std;

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

int best_path(int N, int K, int H[][2], int L[]) {
  int n = N;
  int k = K;
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < n - 1; ++i) {
    int x = H[i][0];
    int y = H[i][1];
    int z = L[i];
    g[x].emplace_back(y, z);
    g[y].emplace_back(x, z);
  }
  vector<bool> removed(n, false);
  vector<int> sz(n);
  vector<int> pv(n);
  function<void(int)> DFS = [&](int v) -> void {
    sz[v] = 1;
    for (auto [u, _] : g[v]) {
      if (u != pv[v] && !removed[u]) {
        pv[u] = v;
        DFS(u);
        sz[v] += sz[u];
      }
    }
  };
  auto GetCenter = [&](int r) {
    pv[r] = -1;
    DFS(r);
    int tot = sz[r];
    while (true) {
      int nr = -1;
      for (auto [u, _] : g[r]) {
        if (u != pv[r] && !removed[u] && sz[u] * 2 > tot) {
          nr = u;
          break;
        }
      }
      if (nr == -1) {
        return r;
      }
      r = nr;
    }
  };
  int ans = n;
  int iter = 0;
  vector<int> aux(k + 1, 0);
  vector<int> dp(k + 1, 0);
  function<void(int, int, int, int)> Find = [&](int v, int pv, int dist, int depth) -> void {
    if (dist > k) {
      return;
    }
    if (aux[k - dist] == iter) {
      ans = min(ans, dp[k - dist] + depth);
    }
    if (dist == k) {
      ans = min(ans, depth);
    }
    for (auto [u, w] : g[v]) {
      if (!removed[u] && u != pv) {
        Find(u, v, dist + w, depth + 1);
      }
    }
  };
  function<void(int, int, int, int) Calc = [&](int v, int pv, int dist, int depth) -> void {
    if (dist > k) {
      return;
    }
    if (aux[dist] < iter) {
      aux[dist] = iter;
      dp[dist] = depth;
    } else
    if (dp[dist] > depth) {
      aux[dist] = iter;
      dp[dist] = depth;
    }
    for (auto [u, w] : g[v]) {
      if (!removed[u] && u != pv) {
        Calc(u, v, dist + w, depth + 1);
      }
    }
  };  
  function<void(int)> Solve = [&](int v) -> void {
    v = GetCenter(v);
    iter += 1;
    for (auto [u, w] : g[v]) {
      if (!removed[u]) {
        Find(Find, u, v, w, 1);
        Calc(Calc, u, v, w, 1);
      }
    }
    removed[v] = true;
    for (auto [u, _] : g[v]) {
      if (!removed[u]) {
        Solve(u);
      }
    }
  };
  Solve(0);
  return (ans == n ? -1 : ans);
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:73:35: error: expression list treated as compound expression in functional cast [-fpermissive]
   73 |   function<void(int, int, int, int) Calc = [&](int v, int pv, int dist, int depth) -> void {
      |                                   ^
race.cpp:73:87: error: template argument 1 is invalid
   73 |   function<void(int, int, int, int) Calc = [&](int v, int pv, int dist, int depth) -> void {
      |                                                                                       ^~~~
race.cpp: In lambda function:
race.cpp:96:30: error: no match for call to '(std::function<void(int, int, int, int)>) (std::function<void(int, int, int, int)>&, std::tuple_element<0, std::pair<int, int> >::type&, int&, std::tuple_element<1, std::pair<int, int> >::type&, int)'
   96 |         Find(Find, u, v, w, 1);
      |                              ^
In file included from /usr/include/c++/10/functional:59,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from race.cpp:1:
/usr/include/c++/10/bits/std_function.h:617:5: note: candidate: '_Res std::function<_Res(_ArgTypes ...)>::operator()(_ArgTypes ...) const [with _Res = void; _ArgTypes = {int, int, int, int}]'
  617 |     function<_Res(_ArgTypes...)>::
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/std_function.h:617:5: note:   candidate expects 4 arguments, 5 provided
race.cpp:97:14: error: 'Calc' was not declared in this scope
   97 |         Calc(Calc, u, v, w, 1);
      |              ^~~~
race.cpp:97:9: error: 'Calc' was not declared in this scope
   97 |         Calc(Calc, u, v, w, 1);
      |         ^~~~