제출 #763984

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

race

#include <bits/stdc++.h>

using namespace std;

const int N = 200005;
const int L = 20;
const int K = 1000005;

vector<pair<int, int>> g[N];
int dep[N];
int tin[N], tout[N], par[L][N];
long long wt[N];
vector<int> cd[N];
int fa[N], sz[N];
bool rmv[N];
vector<int> child[N];
int mn[K];
int real_k;
int dfs_t = 0;

void pre_dfs(int u, int p, int d, long long w) {
  dep[u] = d;
  wt[u] = w;
  tin[u] = ++dfs_t;
  par[0][u] = p;
  for (auto &e : g[u]) {
    int v, l;
    tie(v, l) = e;
    if (v != p) {
      pre_dfs(v, u, d + 1, w + l);
    }
  }
  tout[u] = dfs_t;
}

bool is_ancs(int u, int v) {
  return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int lca(int u, int v) {
  if (is_ancs(u, v)) return u;
  if (is_ancs(v, u)) return v;
  for (int j = L - 1; j >= 0; j--) {
    if (!is_ancs(par[j][v], u)) {
      v = par[j][v];
    }
  }
  return par[0][v];
}

void dfs(int u, int p) {
  sz[u] = 1;
  for (auto &e : g[u]) {
    int v, w;
    tie(v, w) = e;
    if (!rmv[v] && v != p) {
      dfs(v, u);
      sz[u] += sz[v];
    }
  }
}

int centroid(int u, int p, int n) {
  for (auto &e : g[u]) {
    int v, w;
    tie(v, w) = e;
    if (v != p && !rmv[v]) {
      if (sz[v] > n / 2) {
        return centroid(v, u, n);
      }
    }
  }
  return u;
}

void decompose(int u, int p) {
  dfs(u, p);
  int n = sz[u];
  int c = centroid(u, u, n);
  if (p == -1) {
    fa[c] = c;
  } else {
    fa[c] = p;
    cd[c].emplace_back(p);
    cd[p].emplace_back(c);
  }
  rmv[c] = true;
  for (auto &e : g[c]) {
    int v, w;
    tie(v, w) = e;
    if (!rmv[v]) {
      decompose(v, c);
    }
  }
}

void cd_dfs(int u, int p) {
  child[u].emplace_back(u);
  for (auto &v : cd[u]) {
    if (v != p) {
      cd_dfs(v, u);
      for (auto &x : child[v]) {
        child[u].emplace_back(x);
      }
    }
  }
}

int query(int u) {
  int ans = 0x3f3f3f3f;
  vector<int> aff;
  mn[0] = 0;
  aff.emplace_back(0);
  for (auto &v : cd[u]) {
    if (v != fa[u]) {
      for (auto &x : child[v]) {
        long long real_dist = wt[u] + wt[x] - 2 * wt[lca(u, x)];
        int edges = dep[u] + dep[x] - 2 * dep[lca(u, x)];
        if (real_dist <= real_k) {
          ans = min(ans, edges + mn[real_k - real_dist]);
        }
      }
      for (auto &x : child[v]) {
        long long real_dist = wt[u] + wt[x] - 2 * wt[lca(u, x)];
        int edges = dep[u] + dep[x] - 2 * dep[lca(u, x)];
        if (real_dist <= real_k) {
          aff.emplace_back(real_dist);
          mn[real_dist] = min(mn[real_dist], edges);
        }
      }
    }
  }
  for (auto &x : aff) {
    mn[x] = 0x3f3f3f3f;
  }
  return ans;
}

int best_path(int n, int k, int h[][2], int l[]) {
  memset(mn, 0x3f, sizeof(mn));
  real_k = k;
  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]);
  }
  pre_dfs(0, 0, 0, 0);
  for (int j = 1; j < L; j++) {
    for (int i = 0; i < n; i++) {
      par[j][i] = par[j - 1][par[j - 1][i]];
    }
  }
  dfs(0, 0);
  int root = centroid(0, 0, n);
  decompose(0, -1);
  cd_dfs(root, root);
  int ans = 0x3f3f3f3f;
  for (int i = 0; i < n; i++) {
    ans = min(ans, query(i));
  }
  return (ans == 0x3f3f3f3f ? -1 : ans);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  return 0;
}

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

/usr/bin/ld: /tmp/ccUhuJCG.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccipXTTG.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status