Submission #1092031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092031		juicy	Evacuation plan (IZhO18_plan)	C++17	100 / 100	345 ms	52212 KiB

plan

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
 
const int N = 1e5 + 5, LG = 17, inf = 1e9;
 
int n, m;
int d[N], lab[N], dep[N], pr[LG][N], a[LG][N];
vector<array<int, 2>> g[N];
vector<int> tree[N];
 
int find(int u) {
  return lab[u] < 0 ? u : lab[u] = find(lab[u]);
}
 
bool mrg(int u, int v) {
  if ((u = find(u)) == (v = find(v))) {
    return 0;
  }
  if (lab[u] > lab[v]) {
    swap(u, v);
  }
  lab[u] += lab[v];
  lab[v] = u;
  return 1;
}
 
void dfs(int u) {
  for (int v : tree[u]) {
    if (v ^ pr[0][u]) {
      dep[v] = dep[u] + 1;
      pr[0][v] = u;
      a[0][v] = d[v];
      for (int j = 1; j < LG; ++j) {
        pr[j][v] = pr[j - 1][pr[j - 1][v]];
        a[j][v] = min(a[j - 1][v], a[j - 1][pr[j - 1][v]]);
      }
      dfs(v);
    }
  }
}
 
int qry(int u, int v) {
  int res = inf;
  if (dep[u] < dep[v]) {
    swap(u, v);
  }
  for (int j = LG - 1; ~j; --j) {
    if (dep[u] - (1 << j) >= dep[v]) {
      res = min(res, a[j][u]);
      u = pr[j][u];
    }
  }
  if (u == v) {
    return min(res, d[u]);
  }
  for (int j = LG - 1; ~j; --j) {
    if (pr[j][u] ^ pr[j][v]) {
      res = min({res, a[j][u], a[j][v]});
      u = pr[j][u];
      v = pr[j][v];
    }
  }
  return min({res, d[u], d[v], d[pr[0][u]]});
}
 
int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
 
  cin >> n >> m;
  vector<array<int, 3>> e;
  while (m--) {
    int u, v, w; cin >> u >> v >> w;
    g[u].push_back({v, w});
    g[v].push_back({u, w});
    e.push_back({w, u, v});
  }  
  priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> pq;
  memset(d, 0x3f, sizeof(d));
  int k; cin >> k;
  while (k--) {
    int s; cin >> s;
    pq.push({d[s] = 0, s});
  }
  while (pq.size()) {
    auto [c, u] = pq.top(); pq.pop();
    if (c != d[u]) {
      continue;
    }
    for (auto [v, w] : g[u]) {
      if (d[v] > d[u] + w) {
        pq.push({d[v] = d[u] + w, v});
      }
    }
  }
  for (auto &[w, u, v] : e) {
    w = min(d[u], d[v]);
  }
  sort(e.rbegin(), e.rend());
  memset(lab, -1, sizeof(lab));
  for (auto [w, u, v] : e) {
    if (mrg(u, v)) {
      tree[u].push_back(v);
      tree[v].push_back(u);
    }
  }
  dfs(1);
  int q; cin >> q;
  while (q--) {
    int u, v; cin >> u >> v;
    cout << qry(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