Submission #986256

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
986256	2024-05-20T07:12:42 Z	chautanphat	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KB

race

#include "race.h"

const int N = 2e5, W = 1e6;
int n, k, child[N], f[W], ans = N;
bool del[N];
vector<pair<int, int>> a[N];

void cntSize(int u, int pre = 0)
{
    child[u] = 1;
    for (int i = 0; i < (int)a[u].size(); i++)
    {
        int v = a[u][i].first;
        if (v == pre || del[v]) continue;
        cntSize(v, u);
        child[u] += child[v];
    }
}

int centroid(int u, int sz, int pre = 0)
{
    for (int i = 0; i < (int)a[u].size(); i++)
    {
        int v = a[u][i].first;
        if (v != pre && !del[v] && child[v] > sz/2) return centroid(v, sz, u);
    }
    return u;
}

void cal(int u, int dis, int mode, int pre = 0, int h = 1)
{
    if (dis > k) return;
    if (!mode)
        ans = min(ans, h+f[k-dis]);
    else f[dis] = min(f[dis], h);
    for (int i = 0; i < (int)a[u].size(); i++)
    {
        int v = a[u][i].first, w = a[u][i].second;
        if (del[v] || v == pre) continue;
        cal(v, dis+w, mode, u, h+1);
    }
}

void reset(int u, int dis, int pre = 0)
{
    if (dis > k) return;
    f[dis] = N;
    for (int i = 0; i < (int)a[u].size(); i++)
    {
        int v = a[u][i].first, w = a[u][i].second;
        if (del[v] || v == pre) continue;
        reset(v, dis+w, u);
    }
}

void decompose(int u)
{
    cntSize(u);
    int root = centroid(u, child[u]);
    del[root] = 1;

    for (int i = 0; i < (int)a[root].size(); i++)
    {
        int v = a[root][i].first, w = a[root][i].second;
        if (del[v]) continue;
        cal(v, w, 0);
        cal(v, w, 1);
    }

    for (int i = 0; i < (int)a[root].size(); i++)
    {
        int v = a[root][i].first, w = a[root][i].second;
        if (del[v]) continue;
        reset(v, w);
    }

    for (int i = 0; i < (int)a[root].size(); i++)
        if (!del[a[root][i].first]) decompose(a[root][i].first);
}

int best_path(int N1, int K, int H[][2], int L[])
{
  for (int i = 1; i <= k; i++) f[i] = N;
  for (int i = 0; i < N1; i++)
  {
    a[H[i][0]].push_back({H[i][1], L[i]});
    a[H[i][1]].push_back({H[i][0], L[i]});
  }

  n = N1, k = K;
  decompose(0);

  return (ans == N ? -1 : ans);
}

Compilation message

race.cpp:6:1: error: 'vector' does not name a type
    6 | vector<pair<int, int>> a[N];
      | ^~~~~~
race.cpp: In function 'void cntSize(int, int)':
race.cpp:11:30: error: 'a' was not declared in this scope
   11 |     for (int i = 0; i < (int)a[u].size(); i++)
      |                              ^
race.cpp: In function 'int centroid(int, int, int)':
race.cpp:22:30: error: 'a' was not declared in this scope
   22 |     for (int i = 0; i < (int)a[u].size(); i++)
      |                              ^
race.cpp: In function 'void cal(int, int, int, int, int)':
race.cpp:34:15: error: 'min' was not declared in this scope
   34 |         ans = min(ans, h+f[k-dis]);
      |               ^~~
race.cpp:35:19: error: 'min' was not declared in this scope
   35 |     else f[dis] = min(f[dis], h);
      |                   ^~~
race.cpp:36:30: error: 'a' was not declared in this scope
   36 |     for (int i = 0; i < (int)a[u].size(); i++)
      |                              ^
race.cpp:40:20: error: 'w' was not declared in this scope
   40 |         cal(v, dis+w, mode, u, h+1);
      |                    ^
race.cpp: In function 'void reset(int, int, int)':
race.cpp:48:30: error: 'a' was not declared in this scope
   48 |     for (int i = 0; i < (int)a[u].size(); i++)
      |                              ^
race.cpp:52:22: error: 'w' was not declared in this scope
   52 |         reset(v, dis+w, u);
      |                      ^
race.cpp: In function 'void decompose(int)':
race.cpp:62:30: error: 'a' was not declared in this scope
   62 |     for (int i = 0; i < (int)a[root].size(); i++)
      |                              ^
race.cpp:66:16: error: 'w' was not declared in this scope
   66 |         cal(v, w, 0);
      |                ^
race.cpp:70:30: error: 'a' was not declared in this scope
   70 |     for (int i = 0; i < (int)a[root].size(); i++)
      |                              ^
race.cpp:74:18: error: 'w' was not declared in this scope
   74 |         reset(v, w);
      |                  ^
race.cpp:77:30: error: 'a' was not declared in this scope
   77 |     for (int i = 0; i < (int)a[root].size(); i++)
      |                              ^
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:86:5: error: 'a' was not declared in this scope
   86 |     a[H[i][0]].push_back({H[i][1], L[i]});
      |     ^