Submission #529248

#	Time	Username	Problem	Language	Result	Execution time	Memory
529248		Alex_tz307	Factories (JOI14_factories)	C++17	100 / 100	5014 ms	194928 KiB

factories

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

using namespace std;

const int kN = 5e5;
const int kLog = 18;
const int64_t INF = 2e18L;
int M, qIndex, tin[1 + kN], tour[2 * kN], depth[1 + kN], sz[1 + kN], p[1 + kN], curr[1 + kN], lg2[2 * kN], rmq[2 * kN][1 + kLog + 1];
int64_t dp[1 + kN], best[1 + kN];
vector<pair<int, int>> g[1 + kN];
bitset<1 + kN> vis;
vector<int> modified;

void precalc() {
  for (int i = 2; i < 2 * kN; ++i) {
    lg2[i] = lg2[i / 2] + 1;
  }
}

void minSelf(int64_t &x, int64_t y) {
  if (y < x) {
    x = y;
  }
}

void dfs(int u, int par) {
  depth[u] = depth[par] + 1;
  tin[u] = ++M;
  tour[M] = u;
  for (auto it : g[u]) {
    int v, w;
    tie(v, w) = it;
    if (v != par) {
      dp[v] = dp[u] + w;
      dfs(v, u);
      tour[++M] = u;
    }
  }
}

void buildRmq() {
  for (int i = 1; i <= M; ++i) {
    rmq[i][0] = tour[i];
  }
  for (int j = 1; (1 << j) <= M; ++j) {
    for (int i = 1; i + (1 << j) - 1 <= M; ++i) {
      rmq[i][j] = rmq[i][j - 1];
      if (depth[rmq[i + (1 << (j - 1))][j - 1]] < depth[rmq[i][j]]) {
        rmq[i][j] = rmq[i + (1 << (j - 1))][j - 1];
      }
    }
  }
}

void findSize(int u, int par) {
  sz[u] = 1;
  for (auto it : g[u]) {
    int v = it.first;
    if (!vis[v] && v != par) {
      findSize(v, u);
      sz[u] += sz[v];
    }
  }
}

int findCentroid(int u, int par, int n) {
  for (auto it : g[u]) {
    int v = it.first;
    if (!vis[v] && v != par && sz[v] > n / 2) {
      return findCentroid(v, u, n);
    }
  }
  return u;
}

void build(int u, int par) {
  findSize(u, 0);
  int c = findCentroid(u, 0, sz[u]);
  vis[c] = true;
  p[c] = par;
  for (auto it : g[c]) {
    int v = it.first;
    if (!vis[v]) {
      build(v, c);
    }
  }
}

int getLca(int u, int v) {
  if (tin[v] < tin[u]) {
    swap(u, v);
  }
  int diff = tin[v] - tin[u] + 1;
  int k = lg2[diff];
  int shift = diff - (1 << k);
  if (depth[rmq[tin[u]][k]] < depth[rmq[tin[u] + shift][k]]) {
    return rmq[tin[u]][k];
  }
  return rmq[tin[u] + shift][k];
}

int64_t getDist(int u, int v, int lca) {
  return dp[u] + dp[v] - 2 * dp[lca];
}

void update(int u) {
  best[u] = 0;
  int v = u;
  while (v) {
    if (curr[v] != qIndex) {
      curr[v] = qIndex;
      modified.emplace_back(v);
    }
    minSelf(best[v], getDist(u, v, getLca(u, v)));
    v = p[v];
  }
}

int64_t query(int u) {
  int64_t ans = INF;
  int v = u;
  while (v) {
    minSelf(ans, best[v] + getDist(u, v, getLca(u, v)));
    v = p[v];
  }
  return ans;
}

void Init(int n, int a[], int b[], int d[]) {
  precalc();
  for (int i = 0; i <= n - 2; ++i) {
    a[i] += 1;
    b[i] += 1;
    g[a[i]].emplace_back(b[i], d[i]);
    g[b[i]].emplace_back(a[i], d[i]);
  }
  dfs(1, 0);
  buildRmq();
  build(1, 0);
  for (int v = 1; v <= n; ++v) {
    best[v] = INF;
  }
}

long long Query(int n, int x[], int m, int y[]) {
  qIndex += 1;
  modified.clear();
  for (int i = 0; i < n; ++i) {
    x[i] += 1;
    update(x[i]);
  }
  int64_t ans = INF;
  for (int i = 0; i < m; ++i) {
    y[i] += 1;
    minSelf(ans, query(y[i]));
  }
  for (int v : modified) {
    best[v] = INF;
  }
  return ans;
}

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