Submission #993765

#	Time	Username	Problem	Language	Result	Execution time	Memory
993765		Szil	Factories (JOI14_factories)	C++17	0 / 100	23 ms	28296 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<int, ll>> g[MAXN];
vector<int> g2[MAXN];
int 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++) {
    up[u][i] = up[up[u][i-1]][i-1];
  }
}

void dfs2(int u) {
  for (int v : g2[u]) {
    par[v] = u;
    dfs2(v);
  }
}

int findc(int u, int p = -1) {
  for (auto [v, d] : g[u]) {
    if (!vis[v] && v != p && sz[v] > n/2) return findc(v, u);
  }
  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 (!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] - 2 * depth[l];
}

int build_tree(int u) {
  calc_sz(u);
  int c = findc(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);
      g2[idx[c]].emplace_back(idx[x]);
    }
  }
  return c;
}

void Init(int N, int A[], int B[], int D[]) {
  fill(mn, mn+MAXN, 1e18);
  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);
  dfs2(1);
}

long long Query(int S, int X[], int T, int Y[]) {
  ll ans = 1e18;
  auto work = [&](int u, int goal, bool rem) {
    while (u != 0) {
      mn[u] = rem ? 1e18 : 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