Submission #1088553

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1088553	2024-09-14T15:23:08 Z	LucasLe	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KB

race

#include <bits/stdc++.h>

#define              moony  long long
#define                pii  pair<int, int>
#define                 fi  first
#define                 se  second
#define                 ld  long double
#define                 vi  vector<int>
#define                vii  vector<vector<int>>
#define             all(v)  (v).begin(), (v).end()
#define       rep(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i)
#define       per(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i)

using namespace std;

const int MOD = 1e9 + 7;

int add(int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}

int mul(int a, int b) {
  (a *= b) %= MOD;
  return a;
}

int ceil(int x, int y) {
  return (x + y - 1) / y;
}

int bin_pow(int x, int y) {
  int res=1;
  while(y){if(y&1)res=res*x%MOD;x=x*x%MOD;y>>=1;}
  return res;
}

const int INF = 1e9;
const int maxn = 1e6 + 5;

int n, k, ans, mx;
int sz[maxn + 5], d[maxn + 5];
bool vis[maxn + 5];
vector<pair<int, int>> g[maxn + 5];

void count_child(int u, int p) {
  sz[u] = 1;
  for (auto [v, c] : g[u]) {
    if (v == p || vis[v]) continue;
    count_child(v, u);
    sz[u] += sz[v];
  }
}

int find_centroid(int u, int p, int m) {
  for (auto [v, c] : g[u]) {
    if (v == p || vis[v]) continue;
    if (sz[v] > m / 2) return find_centroid(v, u, m);
  }
  return u;
}

void dfs(int u, int p, int sum, int h, bool status) {
  if (sum <= k) {
    if (!status) {
      ans = min(ans, h + d[k - sum]);
    } else {
      d[sum] = min(d[sum], h);
    }
    mx = max(mx, sum);
  }
  for (auto [v, cost] : g[u]) {
    if (v == p || vis[v]) continue;
    dfs(v, u, min(sum + cost, k + 1), h + 1, status);
  }
}

int CT(int u) {
  count_child(u, 0);
  int m = sz[u];
  int c = find_centroid(u, 0, m);
  vis[c] = true;
  d[0] = 0; mx = 0;
  for (auto [v, cost] : g[c]) {
    if (vis[v]) continue;
    dfs(v, c, cost, 1, false);
    dfs(v, c, cost, 1, true);
  }
  fill(d, d + mx + 1, INF);
  for (auto [v, cost] : g[c]) {
    if (vis[v]) continue;
    CT(v);
  }
  return c;
}

int best_path(int N, int K, vector<vector<int>> H, vector<int> L) {
  n = N, k = K;
  for (int i = 0; i < n - 1; ++i) {
    int u = H[i][0];
    int v = H[i][1];
    int c = L[i];
    g[u].push_back({v, c});
    g[v].push_back({u, c});
  }
  fill(d, d + n + 1, INF);
  ans = INF;
  CT(1);
  return (ans == INF ? -1 : ans);
}

Compilation message

/usr/bin/ld: /tmp/ccDqNjFH.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status