Submission #855848

#	Time	Username	Problem	Language	Result	Execution time	Memory
855848		rxlfd314	Factories (JOI14_factories)	C++17	100 / 100	2985 ms	451924 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using arl2 = array<ll, 2>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

#define chmax(a, b) a = a > (b) ? a : (b)
#define chmin(a, b) a = a < (b) ? a : (b)

static constexpr int mxN = 500000;
static vt<ari2> adj[mxN];
static vt<arl2> cdal[mxN];
static vt<int> cd[mxN];
static ll best[mxN];

void Init(int N, int A[], int B[], int D[]) {
  FOR(i, 0, N-2) {
    adj[A[i]].push_back({B[i], D[i]});
    adj[B[i]].push_back({A[i], D[i]});
  }
  int szs[N];
  bool dead[N] = {};
  function<int(int, int)> gs = [&](int i, int p) {
    szs[i] = 1;
    for (auto [j, _] : adj[i])
      if (!dead[j] && j != p)
        szs[i] += gs(j, i);
    return szs[i];
  };
  auto fc = [&](int i, int n) {
    bool flag = true;
    int p = i;
    while (flag) {
      flag = false;
      for (auto [j, _] : adj[i])
        if (!dead[j] && j != p && szs[j] > n >> 1) {
          p = i;
          i = j;
          flag = true;
          break;
        }
    }
    return i;
  };
  int root;
  function<void(int, int)> init = [&](int i, int p) {
    int c = fc(i, gs(i, i));
    dead[c] = true;
    if (~p)
      cd[p].push_back(c);
    else
      root = c;
    for (auto [j, _] : adj[c])
      if (!dead[j])
        init(j, c);
  };
  init(0, -1);
  
  const int L = 32 - __builtin_clz(N);
  vt<vt<int>> lift(N, vt<int>(L));
  int tin[N], tout[N], timer = 0;
  ll depth[N] = {};
  function<void(int, int)> pc = [&](int i, int p) {
    lift[i][0] = p;
    tin[i] = timer++;
    for (auto [j, v] : adj[i]) {
      if (j == p)
        continue;
      depth[j] = depth[i] + v;
      pc(j, i);
    }
    tout[i] = timer - 1;
  };
  pc(0, 0);
  FOR(j, 1, L-1)
    FOR(i, 0, N-1)
      lift[i][j] = lift[lift[i][j-1]][j-1];
  auto ia = [&](int a, int b) {
    return tin[a] <= tin[b] && tin[b] <= tout[a];
  };
  auto LCA = [&](int a, int b) {
    if (ia(a, b))
      return a;
    if (ia(b, a))
      return b;
    ROF(i, L-1, 0)
      a = ia(lift[a][i], b) ? a : lift[a][i];
    return lift[a][0];
  };
  auto dist = [&](int a, int b) {
    return depth[a] + depth[b] - 2 * depth[LCA(a, b)];
  };
  function<void(int)> pc_cdal = [&](int i) {
    cdal[i].push_back({i, 0});
    for (int j : cd[i]) {
      for (auto [a, _] : cdal[i])
        cdal[j].push_back({a, dist(a, j)});
      pc_cdal(j);
    }
  };
  pc_cdal(root);
  memset(best, 0x3f, sizeof(best));
}

ll Query(int S, int X[], int T, int Y[]) {
  FOR(i, 0, S-1)
    for (auto [a, b] : cdal[X[i]])
      chmin(best[a], b);
  ll ret = LLONG_MAX;
  FOR(i, 0, T-1)
    for (auto [a, b] : cdal[Y[i]])
      chmin(ret, best[a] + b);
  FOR(i, 0, S-1)
    for (auto [a, _] : cdal[X[i]])
      best[a] = 0x3f3f3f3f3f3f3f3f;
  return ret;
}

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