제출 #235570

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
235570		ADMathNoob	공장들 (JOI14_factories)	C++11	0 / 100	1290 ms	524292 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;
      assert(0 <= u && u < n);
      if (u == pv[v] || cdepth[u] != -1) {
        continue;
      }
      if (sz[u] > sz[v] / 2) {
        v = u;
        ok = false;
        break;
      }
    }
    if (ok) {
      return v;
    }
  }
  assert(0);
}

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;
// }

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67