Submission #677944

#	Time	Username	Problem	Language	Result	Execution time	Memory
677944		vjudge1	Evacuation plan (IZhO18_plan)	C++17	100 / 100	553 ms	177020 KiB

plan

#include <bits/stdc++.h>

using namespace std;
using TNode = pair<int64_t, int>;
using TEdge = tuple<int, int, int64_t>;

const int N = 5e5 + 5;
const int LG = __lg(N) + 5;

int n, m;
vector<TNode> g[N], tree[N];
TEdge edges[N];

int k;
int64_t d[N];
int banned[N];

int q;

int h[N];
int f[N][LG];
int64_t mind[N][LG];
int r[N];

void dfs_lca (int u, int par = -1) {
  for (int i = 0; f[f[u][i]][i]; i++) {
    f[u][i + 1] = f[f[u][i]][i];
    mind[u][i + 1] = min(mind[u][i], mind[f[u][i]][i]);
  }
  for (auto [v, w] : tree[u]) {
    if (v == par) {
      continue;
    }
    f[v][0] = u;
    mind[v][0] = w;
    h[v] = h[u] + 1;
    dfs_lca(v, u);
  }
}

int64_t lca (int u, int v) {
  int64_t ans = 9e18;
  if (h[u] < h[v]) {
    swap(u, v);
  }
  for (int dist = h[u] - h[v]; dist > 0; dist = h[u] - h[v]) {
    ans = min(ans, mind[u][__lg(dist)]);
    u = f[u][__lg(dist)];
  }
  if (u == v) {
    return ans;
  }
  for (int i = __lg(h[u]); i >= 0; i--) {
    if (f[u][i] != f[v][i]) {
      ans = min({ans, mind[u][i], mind[v][i]});
      u = f[u][i];
      v = f[v][i];
    }
  }

  return min({ans, mind[u][0], mind[v][0]});
}

int root (int u) {
  return r[u] < 0 ? u : r[u] = root(r[u]);
}

bool join (int u, int v) {
  u = root(u);
  v = root(v);
  if (u == v) {
    return false;
  }
  if (r[u] > r[v]) {
    swap(u, v);
  }
  r[u] += r[v];
  r[v] = u;
  return true;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    auto &[u, v, w] = edges[i];
    cin >> u >> v >> w;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
  }

  memset(d, 0x3f, sizeof(d));
  priority_queue<TNode, vector<TNode>, greater<TNode>> pq;

  cin >> k;
  while (k--) {
    int u;
    cin >> u;
    d[u] = 0;
    pq.emplace(d[u], u);
  }

  while (!pq.empty()) {
    auto [du, u] = pq.top();
    pq.pop();

    if (d[u] != du) {
      continue;
    }

    for (auto [v, w] : g[u]) {
      if (d[v] > d[u] + w) {
        d[v] = d[u] + w;
        pq.emplace(d[v], v);
      }
    }
  }

  for (int i = 1; i <= m; i++) {
    auto &[u, v, w] = edges[i];
    w = min(d[u], d[v]);
  }

  memset(r, -1, sizeof(r));
  sort(edges + 1, edges + m + 1, [&](TEdge u, TEdge v) {
    return get<2>(u) > get<2>(v);
  });

  for (int i = 1; i <= m; i++) {
    auto [u, v, w] = edges[i];
    if (join(u, v)) {
      tree[u].emplace_back(v, w);
      tree[v].emplace_back(u, w);
    }
  }

  memset(mind, 0x3f, sizeof(mind));
  h[1] = 1;
  dfs_lca(1);

  cin >> q;
  while (q--) {
    int u, v; cin >> u >> v;
    cout << lca(u, v) << "\n";
  }

  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46