Submission #989597

#	Time	Username	Problem	Language	Result	Execution time	Memory
989597		tch1cherin	Evacuation plan (IZhO18_plan)	C++17	100 / 100	398 ms	35268 KiB

plan

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

struct dsu {
  vector<int> parent, rank;
  vector<pair<int, int>> parent_old, rank_old;

  dsu() {}

  dsu(int n) : parent(n), rank(n, 1) {
    iota(parent.begin(), parent.end(), 0);
  }

  int get(int u) {
    return parent[u] == u ? u : get(parent[u]);
  }

  bool unite(int u, int v) {
    u = get(u), v = get(v);
    if (u != v) {
      if (rank[u] < rank[v]) {
        swap(u, v);
      }
      rank_old.push_back({u, rank[u]});
      parent_old.push_back({v, parent[v]});
      rank[u] += rank[v];
      parent[v] = u;
      return true;
    }
    return false;
  }

  void rollback() {
    rank[rank_old.back().first] = rank_old.back().second;
    parent[parent_old.back().first] = parent_old.back().second;
    rank_old.pop_back(), parent_old.pop_back();
  }
};

const int MAX_N = 100000;
const int INF = 1e9;
vector<pair<int, int>> graph[MAX_N];
vector<int> S, T, dist, answer;
vector<int> sorted_v, pos_v;
dsu sets;

void parallel_bs(vector<int> queries, int L, int R) {
  if (R - L == 1) {
    for (int i : queries) {
      answer[i] = dist[sorted_v[L]];
    }
  } else {
    int mid = (L + R) / 2;
    int cnt_upd = 0;
    for (int i = L; i < mid; i++) {
      for (auto [j, w] : graph[sorted_v[i]]) {
        if (pos_v[j] < mid) {
          cnt_upd += sets.unite(sorted_v[i], j);
        }
      }
    }
    vector<int> q_left, q_right;
    for (int i : queries) {
      if (sets.get(S[i]) == sets.get(T[i])) {
        q_left.push_back(i);
      } else {
        q_right.push_back(i);
      }
    }
    vector<int>().swap(queries);
    parallel_bs(q_right, mid, R);
    while (cnt_upd--) {
      sets.rollback();
    }
    vector<int>().swap(q_right);
    parallel_bs(q_left, L, mid);
    vector<int>().swap(q_left);
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b, w;
    cin >> a >> b >> w;
    a--, b--;
    graph[a].push_back({b, w});
    graph[b].push_back({a, w});
  }
  int k;
  cin >> k;
  vector<int> cities(k);
  for (int &value : cities) {
    cin >> value;
    value--;
  }
  int Q;
  cin >> Q;
  S = T = vector<int>(Q);
  for (int i = 0; i < Q; i++) {
    cin >> S[i] >> T[i];
    S[i]--, T[i]--;
  }
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
  dist.assign(n, INF);
  pos_v.resize(n);
  for (int u : cities) {
    que.push({dist[u] = 0, u});
  }
  while (!que.empty()) {
    auto [d, u] = que.top();
    que.pop();
    if (d > dist[u]) {
      continue;
    }
    sorted_v.push_back(u);
    pos_v[u] = n - (int)sorted_v.size();
    for (auto [v, w] : graph[u]) {
      if (dist[v] > dist[u] + w) {
        que.push({dist[v] = dist[u] + w, v});
      }
    }
  }
  reverse(sorted_v.begin(), sorted_v.end());
  answer.resize(Q);
  sets = dsu(n);
  vector<int> queries(Q);
  iota(queries.begin(), queries.end(), 0);
  parallel_bs(queries, 0, n);
  for (int i = 0; i < Q; i++) {
    cout << answer[i] << "\n";
  }
}

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