제출 #993801

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
993801		Szil	공장들 (JOI14_factories)	C++17	0 / 100	21 ms	123484 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 500'001;
const int K = 21;

vector<pair<ll, ll>> g[MAXN];
ll sz[MAXN], tin[MAXN], tout[MAXN], up[MAXN][K], idx[MAXN], node[MAXN], par[MAXN], timer = 1, n;
ll mn[MAXN];
bool vis[MAXN];
ll depth[MAXN];

void calc_sz(int u, int p = -1) {
  sz[u] = 1;
  for (auto [v, d] : g[u]) {
    if (vis[v] || v == p) continue;
    calc_sz(v, u);
    sz[u] += sz[v];
  }
}

void dfs(int u, int p = -1) {
  tin[u] = timer++;
  for (auto [v, d] : g[u]) {
    if (v == p) continue;
    depth[v] = depth[u] + d;
    dfs(v, u);
    up[v][0] = u;
  }
  tout[u] = timer++;
  for (int i = 1; i < K; i++) {
    if (up[u][i-1] != -1) {
      up[u][i] = up[up[u][i-1]][i-1];
    }
  }
}

int findc(int u, int p, int siz) {
  for (auto [v, d] : g[u]) {
    if (!vis[v] && v != p && sz[v] > siz/2) return findc(v, u, siz);
  }
  return u;
} 

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

int lca(int u, int v) {
  if (is_ancestor(u, v)) return u;
  if (is_ancestor(v, u)) return v;
  for (int i = K-1; i >= 0; i--) {
    if (up[u][i] != -1 && !is_ancestor(up[u][i], v)) u = up[u][i];
  }
  return up[u][0];
}

ll get_dist(int u, int v) {
  int l = lca(u, v);
  return depth[u] + depth[v] - 2ll * depth[l];
}

int build_tree(int u) {
  calc_sz(u);
  int c = findc(u, -1, sz[u]);
  idx[c] = timer;
  node[timer] = c;
  timer++;
  vis[c] = true;
  for (auto [v, d] : g[c]) {
    if (!vis[v]) {
      int x = build_tree(v);
      par[idx[x]] = idx[c];
    }
  }
  return c;
}

void Init(int N, int A[], int B[], int D[]) {
  fill(mn, mn+MAXN, 1e16);
  for (int i = 0; i < MAXN; i++) {
    for (int j = 0; j < K; j++) {
      up[i][j] = -1;
    }
  }
  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]);
  }
  dfs(0);
  timer = 1;
  build_tree(0);
}

long long Query(int S, int X[], int T, int Y[]) {
  ll ans = 1e16;
  auto work = [&](int u, int goal, bool rem) {
    while (u != 0) {
      mn[u] = rem ? 1e16 : min(mn[u], get_dist(node[u], goal));
      u = par[u];
    }
  };
  auto calc = [&](int u, int goal) {
    while (u != 0) {
      ans = min(ans, get_dist(node[u], goal) + mn[u]);
      u = par[u];
    }
  };

  for (int i = 0; i < T; i++) {
    work(idx[Y[i]], Y[i], false);
  }

  for (int i = 0; i < S; i++) {
    calc(idx[X[i]], X[i]);
  }

  for (int i = 0; i < T; i++) {
    work(idx[Y[i]], Y[i], true);
  }
  return ans;
}

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