제출 #395272

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
395272		rama_pang	Evacuation plan (IZhO18_plan)	C++17	100 / 100	833 ms	69716 KiB

plan

#include <bits/stdc++.h>
using namespace std;

class DisjointSet {
 public:
  int n;
  vector<int> p;
  DisjointSet() {}
  DisjointSet(int n) : n(n), p(n) {
    iota(begin(p), end(p), 0);
  }
  int Find(int x) {
    return p[x] == x ? x : p[x] = Find(p[x]);
  }
  int Unite(int x, int y) {
    x = Find(x), y = Find(y);
    if (x != y) {
      p.emplace_back(n);
      p[x] = p[y] = n;
      n++;
      return 1;
    }
    return 0;
  }
};

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

  int n, m;
  cin >> n >> m;
  vector<vector<pair<int, int>>> adj(n);
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
  }
  int k;
  cin >> k;
  vector<int> dist(n, -1);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  for (int i = 0; i < k; i++) {
    int g;
    cin >> g;
    g--;
    dist[g] = 0;
    pq.emplace(0, g);
  }

  while (!pq.empty()) {
    int u = pq.top().second;
    int d = pq.top().first;
    pq.pop();
    if (dist[u] != d) {
      continue;
    }
    for (auto e : adj[u]) {
      int v = e.first;
      int w = e.second;
      if (dist[v] == -1 || dist[v] > dist[u] + w) {
        dist[v] = dist[u] + w;
        pq.emplace(dist[v], v);
      }
    }
  }

  vector<int> order(n);
  iota(begin(order), end(order), 0);
  sort(begin(order), end(order), [&](int i, int j) { return dist[i] > dist[j]; });

  DisjointSet D(n);
  vector<int> done(n);
  vector<int> depth(n);
  vector<int> parent(n, -1);
  vector<vector<int>> tree(n);
  for (auto u : order) {
    done[u] = 1;
    for (auto v : adj[u]) {
      if (done[v.first] && D.Find(u) != D.Find(v.first)) {
        int r = tree.size();
        depth.emplace_back();
        tree.emplace_back();
        parent.emplace_back(-1);
        dist.emplace_back(dist[u]);
        tree[r].emplace_back(D.Find(u));
        tree[r].emplace_back(D.Find(v.first));
        assert(D.Unite(u, v.first));
      }
    }
  }

  vector<vector<int>> lift(tree.size(), vector<int>(20, -1));
  function<void(int)> Dfs = [&](int u) {
    lift[u][0] = parent[u];
    for (int j = 1; j < 20; j++) {
      if (lift[u][j - 1] == -1) {
        lift[u][j] = -1;
      } else {
        lift[u][j] = lift[lift[u][j - 1]][j - 1];
      }
    }
    for (auto v : tree[u]) {
      depth[v] = depth[u] + 1;
      parent[v] = u;
      Dfs(v);
      dist[u] = min(dist[u], dist[v]);
    }
  };
  Dfs(int(tree.size()) - 1);


  int q;
  cin >> q;
  while (q--) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    if (depth[u] > depth[v]) {
      swap(u, v);
    }
    int diff = depth[v] - depth[u];
    for (int i = 0; i < 20; i++) {
      if (diff & (1 << i)) {
        v = lift[v][i];
      }
    }
    for (int i = 19; i >= 0; i--) {
      if (lift[u][i] != lift[v][i]) {
        u = lift[u][i];
        v = lift[v][i];
      }
    }
    if (u != v) {
      u = lift[u][0];
      v = lift[v][0];
    }
    assert(u == v);
    cout << dist[u] << '\n';
  }
  return 0;
}

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