제출 #235567

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
235567		ADMathNoob	공장들 (JOI14_factories)	C++11	컴파일 에러	0 ms	0 KiB

factories

#include <bits/stdc++.h>

#ifndef _DEBUG
#include "factories.h"
#endif

using namespace std;


const long long INF = 1e18;
const int N = 500005;
const int H = 20;

int n;
vector<pair<int, int>> g[N];

int pv[N];
vector<int> order;
long long dist[N];
int sz[N];

int cpv[N];
int cdepth[N];
long long f[H][N];

long long best[N];

void dfs(int v, int p) {
  pv[v] = p;
  sz[v] = 1;
  order.push_back(v);
  for (const auto& e : g[v]) {
    int u = e.first;
    int w = e.second;
    if (u == p || cdepth[u] != -1) {
      continue;
    }
    dist[u] = dist[v] + w;
    dfs(u, v);
    sz[v] += sz[u];
  }
}

void do_dfs_from(int v) {
  order.clear();
  dist[v] = 0;
  dfs(v, -1);
}

int centroid(int v) {
  do_dfs_from(v);
  while (true) {
    bool ok = true;
    assert(0 <= v && v < n);
    for (const auto& e : g[v]) {
      int u = e.first;
      if (u == pv[v] || cdepth[u] != -1) {
        continue;
      }
      if (sz[u] > sz[v] / 2) {
        v = u;
        ok = false;
        break;
      }
    }
    if (ok) {
      break;
    }
  }
  return v;
}

void cdfs(int v, int p) {
  cpv[v] = p;
  do_dfs_from(v);
  for (int i : order) {
    f[cdepth[v]][i] = dist[i];
  }
  // cerr << "centroid: " << v << '\n';
  for (const auto& e : g[v]) {
    int u = e.first;
    if (cdepth[u] != -1) {
      continue;
    }
    u = centroid(u);
    cdepth[u] = cdepth[v] + 1;
    cdfs(u, v);
  }
}

void build_centroid() {
  fill(cdepth, cdepth + N, -1);
  int c = centroid(0);
  cdepth[c] = 0;
  cdfs(c, -1);
}

void Init(int _n, int a[], int b[], int d[]) {
  n = _n;
  for (int i = 0; i < n - 1; i++) {
    g[a[i]].emplace_back(b[i], d[i]);
    g[b[i]].emplace_back(a[i], d[i]);
  }
  build_centroid();
  fill(best, best + N, INF);
}

void update(int v) {
  for (int u = v; u != -1; u = cpv[u]) {
    best[u] = min(best[u], f[cdepth[u]][v]);
  }
}

long long get(int v) {
  long long res = INF;
  for (int u = v; u != -1; u = cpv[u]) {
    res = min(res, f[cdepth[u]][v] + best[u]);
  }
  return res;
}

void reset(int v) {
  while (v != -1) {
    best[v] = INF;
    v = cpv[v];
  }
}

long long Query(int s, int x[], int t, int y[]) {
  for (int i = 0; i < s; i++) {
    update(x[i]);
  }
  long long ans = INF;
  for (int i = 0; i < t; i++) {
    ans = min(ans, get(y[i]));
  }
  for (int i = 0; i < s; i++) {
    reset(x[i]);
  }
  return ans;
}


int a[N], b[N], d[N];
int x[N], y[N];

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

#ifdef _DEBUG
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  freopen("debug_output.txt", "w", stderr);
#endif


  int n, q;
  cin >> n >> q;
  for (int i = 0; i < n - 1; i++) {
    cin >> a[i] >> b[i] >> d[i];
  }
  Init(n, a, b, d);
  while (q--) {
    int s, t;
    cin >> s >> t;
    for (int i = 0; i < s; i++) {
      cin >> x[i];
    }
    for (int i = 0; i < t; i++) {
      cin >> y[i];
    }
    cout << Query(s, x, t, y) << '\n';
  }


  return 0;
}

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

/tmp/cc2VP6d5.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccVzuRal.o:factories.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status