Submission #859170

#	Time	Username	Problem	Language	Result	Execution time	Memory
859170		rxlfd314	Evacuation plan (IZhO18_plan)	C++17	100 / 100	477 ms	44980 KiB

plan

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;

#define vt vector
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

#define chmax(a, b) (a) = (a) > (b) ? (a) : (b)
#define chmin(a, b) (a) = (a) < (b) ? (a) : (b)

void solve();

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  int T = 1;
  //cin >> T;
  FOR(t, 1, T) {
    solve();
  }
}

void solve() {
  int N, M;
  cin >> N >> M;
  vt<ari2> adj[N];
  FOR(i, 1, M) {
    int a, b, c;
    cin >> a >> b >> c;
    adj[--a].push_back({--b, c});
    adj[b].push_back({a, c});
  }
  ll D[N];
  memset(D, 0x3f, sizeof(D));
  int K;
  cin >> K;
  priority_queue<arl2, vt<arl2>, greater<arl2>> pq;
  while (K--) {
    int v;
    cin >> v, v--;
    pq.push({D[v] = 0, v});
  }
  while (size(pq)) {
    auto [_, i] = pq.top();
    pq.pop();
    for (auto [j, v] : adj[i])
      if (D[i] + v < D[j])
        pq.push({D[j] = D[i] + v, j});
  }
  int Q;
  cin >> Q;
  set<int> qrys[N];
  FOR(i, 0, Q-1) {
    int a, b;
    cin >> a >> b;
    qrys[--a].insert(i);
    qrys[--b].insert(i);
  }
  int uf[N];
  memset(uf, -1, sizeof(uf));
  function<int(int)> find = [&](int i) {
    return uf[i] < 0 ? i : uf[i] = find(uf[i]);
  };
  int ord[N];
  iota(ord, ord+N, 0);
  sort(ord, ord+N, [&](const int &a, const int &b) {
    return D[a] > D[b];
  });
  bool active[N] = {};
  ll ans[Q];
  FOR(x, 0, N-1) {
    int i = ord[x];
    active[i] = true;
    for (auto [j, _] : adj[i]) {
      int a = find(i), b = find(j);
      if (!active[j] || a == b)
        continue;
      if (size(qrys[a]) < size(qrys[b]))
        swap(a, b);
      for (int k : qrys[b]) {
        if (qrys[a].count(k)) {
          ans[k] = D[i];
          qrys[a].erase(qrys[a].find(k));
        } else {
          qrys[a].insert(k);
        }
      }
      qrys[b].clear();
      uf[b] = a;
    }
  }
  
  FOR(i, 0, Q-1)
    cout << ans[i] << '\n';
}

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