Submission #235569

#	Time	Username	Problem	Language	Result	Execution time	Memory
235569		ADMathNoob	Factories (JOI14_factories)	C++11	100 / 100	5975 ms	178532 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 = 21;

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);
  for (int i : order) {
    bool ok = (sz[v] - sz[i] <= sz[v] / 2);
    for (const auto& e : g[i]) {
      int u = e.first;
      if (u == pv[i] || cdepth[u] != -1) {
        continue;
      }
      ok &= (sz[u] <= sz[v] / 2);
    }
    if (ok) {
      return i;
    }
  }
  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;
}

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