Submission #529232

#	Time	Username	Problem	Language	Result	Execution time	Memory
529232		Alex_tz307	Factories (JOI14_factories)	C++17	0 / 100	8080 ms	120944 KiB

factories

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

using namespace std;

const int kN = 5e5;
const int kLog = 18;
const int64_t INF = 1e18L;
int N, timer, qIndex, tin[kN], tout[kN], depth[kN], sz[kN], p[kN], curr[kN], lg2[kN], anc[kN][1 + kLog];
int64_t dp[kN], best[kN];
vector<pair<int, int>> g[kN];
bitset<kN> vis;
vector<int> modified;

void precalc() {
  for (int i = 2; i < 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) {
  tin[u] = ++timer;
  for (int i = 1; i <= kLog; ++i) {
    anc[u][i] = anc[anc[u][i - 1]][i - 1];
    if (anc[u][i] == 0) {
      break;
    }
  }
  for (auto it : g[u]) {
    int v, w;
    tie(v, w) = it;
    if (v != anc[u][0]) {
      anc[v][0] = u;
      depth[v] = depth[u] + 1;
      dp[v] = dp[u] + w;
      dfs(v);
    }
  }
  tout[u] = timer;
}

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) {
  for (auto it : g[u]) {
    int v = it.first;
    if (!vis[v] && v != par && sz[v] > N / 2) {
      return findCentroid(v, u);
    }
  }
  return u;
}

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

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

int getLca(int u, int v) {
  if (depth[u] < depth[v]) {
    swap(u, v);
  }
  if (isAncestor(v, u)) {
    return v;
  }
  for (int i = lg2[depth[v]]; i >= 0; --i) {
    if (anc[v][i] && !isAncestor(anc[v][i], u)) {
      v = anc[v][i];
    }
  }
  return anc[v][0];
}

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 != -1) {
    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 != -1) {
    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[]) {
  N = n;
  precalc();
  for (int i = 0; i <= n - 2; ++i) {
    g[a[i]].emplace_back(b[i], d[i]);
    g[b[i]].emplace_back(a[i], d[i]);
  }
  dfs(0);
  build(0, -1);
  for (int v = 0; 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) {
    update(x[i]);
  }
  int64_t ans = INF;
  for (int i = 0; i < m; ++i) {
    minSelf(ans, query(y[i]));
  }
  for (int v : modified) {
    best[v] = INF;
  }
  return ans;
}

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