Submission #399056

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

race

#define INF 0x3f3f3f3f
const int MAXN = 2e5;
const int MAXK = 1e6 + 6;
int sz[MAXN];
vector<pair<int,int>> G[MAXN];
bitset<MAXN> viz;

void find_size(int u, int parent) {
  sz[u] = 1;
  for (auto v : G[u])
    if (v.first != parent && !viz[v.first]) {
      find_size(v.first, u);
      sz[u] += sz[v.first];
    }
}

int find_centroid(int u, int parent, int n) {
  for (auto v : G[u])
    if (v.first != parent && !viz[v.first] && sz[v.first] > (n >> 1))
      return find_centroid(v.first, u, n);
  return u;
}

int ans = INF, k, best_prev[MAXK], best[MAXK], tree_ans;
vector<int> sums;

void min_self(int &a, int b) {
  a = min(a, b);
}

void find_paths(int u, int parent, int sum, int depth) {
  if (sum > k)
    return;
  sums.emplace_back(sum);
  min_self(best[sum], depth);
  min_self(tree_ans, best_prev[k - sum] + best[sum]);
  if (sum == k)
    return;
  for (auto v : G[u])
    if (v.first != parent && !viz[v.first])
      find_paths(v.first, u, sum + v.second, depth + 1);
}

int solve_tree(int u) {
  tree_ans = INF;
  vector<int> all_sums;
  for (auto v : G[u])
    if (!viz[v.first]) {
      find_paths(v.first, u, v.second, 1);
      for (int s : sums) {
        min_self(best_prev[s], best[s]);
        best[s] = INF;
        all_sums.emplace_back(s);
      }
      sums.clear();
    }
  for (int s : all_sums)
    best_prev[s] = INF;
  return tree_ans;
}

int build(int u, int parent) {
  find_size(u, -1);
  int c = find_centroid(u, -1, sz[u]);
  viz[c] = true;
  int ans = solve_tree(c);
  for (auto v : G[c])
    if (!viz[v.first])
      ans = min(ans, build(v.first, c));
  return ans;
}

int best_path(int N, int K, int H[][2], int L[]) {
  for (int i = 0; i < N - 1; ++i) {
    G[H[i][0]].emplace_back(H[i][1], L[i]);
    G[H[i][1]].emplace_back(H[i][0], L[i]);
  }
  k = K;
  for (int s = 1; s <= k; ++s)
    best_prev[s] = best[s] = INF;
  min_self(ans , build(0, -1));
  if (ans == INF)
    ans = -1;
  return ans;
}

Compilation message (stderr)

race.cpp:5:1: error: 'vector' does not name a type
    5 | vector<pair<int,int>> G[MAXN];
      | ^~~~~~
race.cpp:6:1: error: 'bitset' does not name a type
    6 | bitset<MAXN> viz;
      | ^~~~~~
race.cpp: In function 'void find_size(int, int)':
race.cpp:10:17: error: 'G' was not declared in this scope
   10 |   for (auto v : G[u])
      |                 ^
race.cpp:11:31: error: 'viz' was not declared in this scope
   11 |     if (v.first != parent && !viz[v.first]) {
      |                               ^~~
race.cpp: In function 'int find_centroid(int, int, int)':
race.cpp:18:17: error: 'G' was not declared in this scope
   18 |   for (auto v : G[u])
      |                 ^
race.cpp:19:31: error: 'viz' was not declared in this scope
   19 |     if (v.first != parent && !viz[v.first] && sz[v.first] > (n >> 1))
      |                               ^~~
race.cpp: At global scope:
race.cpp:25:1: error: 'vector' does not name a type
   25 | vector<int> sums;
      | ^~~~~~
race.cpp: In function 'void min_self(int&, int)':
race.cpp:28:7: error: 'min' was not declared in this scope
   28 |   a = min(a, b);
      |       ^~~
race.cpp: In function 'void find_paths(int, int, int, int)':
race.cpp:34:3: error: 'sums' was not declared in this scope; did you mean 'sum'?
   34 |   sums.emplace_back(sum);
      |   ^~~~
      |   sum
race.cpp:39:17: error: 'G' was not declared in this scope
   39 |   for (auto v : G[u])
      |                 ^
race.cpp:40:31: error: 'viz' was not declared in this scope
   40 |     if (v.first != parent && !viz[v.first])
      |                               ^~~
race.cpp: In function 'int solve_tree(int)':
race.cpp:46:3: error: 'vector' was not declared in this scope
   46 |   vector<int> all_sums;
      |   ^~~~~~
race.cpp:46:10: error: expected primary-expression before 'int'
   46 |   vector<int> all_sums;
      |          ^~~
race.cpp:47:17: error: 'G' was not declared in this scope
   47 |   for (auto v : G[u])
      |                 ^
race.cpp:48:10: error: 'viz' was not declared in this scope
   48 |     if (!viz[v.first]) {
      |          ^~~
race.cpp:50:20: error: 'sums' was not declared in this scope
   50 |       for (int s : sums) {
      |                    ^~~~
race.cpp:53:9: error: 'all_sums' was not declared in this scope
   53 |         all_sums.emplace_back(s);
      |         ^~~~~~~~
race.cpp:55:7: error: 'sums' was not declared in this scope
   55 |       sums.clear();
      |       ^~~~
race.cpp:57:16: error: 'all_sums' was not declared in this scope
   57 |   for (int s : all_sums)
      |                ^~~~~~~~
race.cpp: In function 'int build(int, int)':
race.cpp:65:3: error: 'viz' was not declared in this scope
   65 |   viz[c] = true;
      |   ^~~
race.cpp:67:17: error: 'G' was not declared in this scope
   67 |   for (auto v : G[c])
      |                 ^
race.cpp:69:13: error: 'min' was not declared in this scope
   69 |       ans = min(ans, build(v.first, c));
      |             ^~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:75:5: error: 'G' was not declared in this scope
   75 |     G[H[i][0]].emplace_back(H[i][1], L[i]);
      |     ^