제출 #1346222

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1346222		eldorbek_008	경주 (Race) (IOI11_race)	C++20	컴파일 에러	0 ms	0 KiB

race

#include <bits/stdc++.h>
using namespace std;

#define int int64_t

int min(int a, int b) {
  return (a < b ? a : b);
}
int max(int a, int b) {
  return (a < b ? b : a);
}

const int inf = 1e18;

int best_path(int n, int k, vector<vector<int>> h, vector<int> l) {
  // ios :: sync_with_stdio(false);
  // cin.tie(nullptr);

  // int n, k;
  // cin >> n >> k;
  // vector<int> l(n);
  // vector<pair<int, int>> h(n);
  // for (int i = 1; i <= n - 1; i++) {
  //   cin >> h[i].first >> h[i].second;
  // }
  // for (int i = 1; i <= n - 1; i++) {
  //   cin >> l[i];
  // }

  vector<vector<pair<int, int>>> g(n + 1);
  for (int i = 1; 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]);
  }

  vector<int> sz(n + 1);
  vector<int> vis(n + 1);

  auto dfs_sz = [&](auto dfs_sz, int u, int p) -> void {
    sz[u] = 1;
    for (auto [v, w] : g[u]) {
      if (v != p and !vis[v]) {
        dfs_sz(dfs_sz, v, u);
        sz[u] += sz[v];
      }
    }
  };

  auto find_c = [&](auto find_c, int u, int p) -> int {
    for (auto [v, w] : g[u]) {
      if (v != p and !vis[v] and sz[v] > n / 2) {
        return find_c(find_c, v, u);
      }
    }
    return u;
  };

  int ans = inf;
  vector<int> edit;
  vector<int> E(k + 1, inf);

  E[0] = 0;

  auto calc = [&](auto calc, int u, int p, int W, int e, int upd) -> void {
    if (W > k)
      return;
    if (upd == 1) {
      // if (E[W] > e) {
        E[W] = e;
        edit.emplace_back(W);
      // }
    } else {
      ans = min(ans, e + E[k - W]);
    }

    for (auto [v, w] : g[u]) {
      if (!vis[v] and v != p) {
        calc(calc, v, u, W + w, e + 1, upd);
      }
    }
  };

  auto solve = [&](auto solve, int u) -> void {
    dfs_sz(dfs_sz, u, -1);
    int centroid = find_c(find_c, u, -1);
    
    vis[centroid] = 1;

    for (auto [v, w] : g[centroid]) {
      if (!vis[v]) {
        calc(calc, v, centroid, w, 1, 0);
        calc(calc, v, centroid, w, 1, 1);
      }
    }

    for (int &x : edit) {
      E[x] = inf;
    }
    edit.clear();

    for (auto [v, w] : g[centroid]) {
      if (!vis[v]) {
        solve(solve, v);
      }
    }
  };

  solve(solve, 0);
  if (ans == inf) {
    return -1;
  } else {
    return ans;
  }

}

컴파일 시 표준 에러 (stderr) 메시지

/usr/bin/ld: /tmp/ccYltYXb.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