Submission #289464

#	Time	Username	Problem	Language	Result	Execution time	Memory
289464		Haunted_Cpp	Factories (JOI14_factories)	C++17	15 / 100	3019 ms	214968 KiB

factories

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

typedef long long i64;

const int MAX_N = 500000 + 5;
const int MAX_K = 20 + 5;
const i64 INF = 1e18;

vector<pair<int, int>> g[MAX_N];

int dp[MAX_N][MAX_K], table[2 * MAX_N][MAX_K];
int sub[MAX_N], del[MAX_N], par[MAX_N], in[MAX_N], depth[MAX_N], L[MAX_N];

i64 d[MAX_N], best_way[MAX_N];

int calc_subtree(int node, int p) {
  sub[node] = 1;
  for (auto to : g[node]) {
    if (to.first != p && !del[to.first]) {
      sub[node] += calc_subtree(to.first, node);
    }
  }
  return sub[node];
}

int calc_centroid(int node, int p, const int tam) {
  for (auto to : g[node]) {
    if (!del[to.first] && to.first != p && sub[to.first] > tam / 2) {
      return calc_centroid(to.first, node, tam);
    }
  }
  return node;
}

void decompose(int node, int p) {
  const int centroid = calc_centroid(node, -1, calc_subtree(node, -1));
  del[centroid] = 1;
  par[centroid] = p;
  for (auto to : g[centroid]) {
    if (!del[to.first]) {
      decompose(to.first, centroid);
    }
  }
}

vector<int> euler;

void prep(int node, int p) {
  in[node] = euler.size();
  euler.emplace_back(node);
  dp[node][0] = p;
  for (auto to : g[node]) {
    if (to.first != p) {
      depth[to.first] = depth[node] + 1;
      d[to.first] = d[node] + to.second;
      prep(to.first, node);
      euler.emplace_back(node);
    }
  }
}

void build_lca() {
  const int n = euler.size();
  for (int i = 0; i < n; i++) {
    table[i][0] = euler[i];
  }
  for (int i = 1; i <= n; i++) {
    L[i] = log2(i);
  }
  for (int j = 1; j < MAX_K; j++) {
    for (int i = 0; i + (1 << j) <= n; i++) {
      int H1 = depth[table[i][j - 1]];
      int H2 = depth[table[i + (1 << (j - 1))][j - 1]];
      table[i][j] = (H1 < H2 ? table[i][j - 1] : table[i + (1 << (j - 1))][j - 1]);
    }
  }
}

int lca(int u, int v) {
  if (in[u] > in[v]) {
    swap(u, v);
  }
  int st = in[u];
  int et = in[v];
  const int k = L[(et - st + 1)];
  int H1 = depth[table[st][k]];
  int H2 = depth[table[et - (1 << k) + 1][k]];
  return (H1 < H2 ? table[st][k] : table[et - (1 << k) + 1][k]);
}

i64 get_dist(int u, int v) {
  return d[u] + d[v] - 2LL * d[lca(u, v)];
}

void paint(int node, bool reset) {
  int start_location = node;
  while(node != -1) {
    if (reset) {
      best_way[node] = INF;
    } else {
      best_way[node] = min(best_way[node], get_dist(start_location, node));
    }
    node = par[node];
  }
}

i64 solve(int node) {
  int start_location = node;
  i64 mn = best_way[node];
  node = par[node];
  while(node != -1) {
    mn = min(mn, get_dist(start_location, node) + best_way[node]);
    node = par[node];
  }
  return mn;
}

void Init(int N, int A[], int B[], int D[]) {
  for (int i = 0; i < N - 1; i++) {
    const int st = A[i];
    const int et = B[i];
    const int w = D[i];
    g[st].emplace_back(et, w);
    g[et].emplace_back(st, w);
  }
  memset(dp, -1, sizeof(dp));
  prep(0, -1);
  build_lca();
  decompose(0, -1);
  for (int i = 0; i < MAX_N; i++) {
    best_way[i] = INF;
  }
}

i64 Query(int S, int X[], int T, int Y[]) {
  i64 mn = INF;
  for (int i = 0; i < S; i++) {
    paint(X[i], false);
  }
  for (int i = 0; i < T; i++) {
    mn = min(mn, solve(Y[i]));
  }
  for (int i = 0; i < S; i++) {
    paint(X[i], true);
  }
  return mn;
}

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