Submission #821742

#	Time	Username	Problem	Language	Result	Execution time	Memory
821742		WLZ	Factories (JOI14_factories)	C++17	100 / 100	5132 ms	149768 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

const long long LINF = (long long) 1e18;

int n, max_log;
vector< vector< pair<int, int> > > g;
vector<int> sz, cd;
vector<bool> used;

int calc_sizes(int u, int par) {
  sz[u] = 1;
  for (auto &[v, w] : g[u]) if (v != par && !used[v]) sz[u] += calc_sizes(v, u);
  return sz[u];
}

int find_centroid(int u, int par, int cur_sz) {
  for (auto &[v, w] : g[u]) if (v != par && !used[v] && sz[v] > cur_sz / 2) return find_centroid(v, u, cur_sz);
  return u;
}

void decompose(int u, int par) {
  int centroid = find_centroid(u, par, calc_sizes(u, par));
  cd[centroid] = par; used[centroid] = true;
  for (auto &[v, w] : g[centroid]) if (!used[v] && v != par) decompose(v, centroid);
}

int dfs_cnt = 0;
vector< vector<int> > up;
vector<int> dfs_in, dfs_out;
vector<long long> depth;

void dfs(int u, int par) {
  dfs_in[u] = dfs_cnt++;
  up[u][0] = par;
  for (int i = 1; i <= max_log; i++) up[u][i] = up[up[u][i - 1]][i - 1];
  for (auto &[v, w] : g[u]) {
    if (v == par) continue;
    depth[v] = depth[u] + w;
    dfs(v, u);
  }
  dfs_out[u] = dfs_cnt++;
}

bool is_anc(int u, int v) {
  return dfs_in[u] <= dfs_in[v] && dfs_out[v] <= dfs_out[u];
}

int lca(int u, int v) {
  if (is_anc(u, v)) return u;
  if (is_anc(v, u)) return v;
  for (int i = max_log; i >= 0; i--) if (!is_anc(up[u][i], v)) u = up[u][i];
  return up[u][0];
}

long long dist(int u, int v) {
  return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}

vector<long long> closest;

void Init(int N, int A[], int B[], int D[]) {
  n = N;
  max_log = ceil(log2(n + 1));
  g.resize(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]);
  }
  cd.resize(n);
  sz.resize(n); used.assign(n, false);
  decompose(0, -1);
  depth.resize(n); depth[0] = 0;
  dfs_in.resize(n); dfs_out.resize(n);
  up.assign(n, vector<int>(max_log + 1));
  dfs(0, 0);
  closest.assign(n, LINF);
}



long long Query(int S, int X[], int T, int Y[]) {
  stack<int> st;
  for (int i = 0; i < S; i++) {
    for (int u = X[i]; u != -1; u = cd[u]) {
      closest[u] = min(closest[u], dist(X[i], u));
      st.push(u);
    }
  }
  long long ans = LINF;
  for (int i = 0; i < T; i++) {
    for (int u = Y[i]; u != -1; u = cd[u]) {
      ans = min(ans, closest[u] + dist(Y[i], u));
    }
  }
  while (!st.empty()) {
    closest[st.top()] = LINF;
    st.pop();
  }
  return ans;
}

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