Submission #935080

#	Time	Username	Problem	Language	Result	Execution time	Memory
935080		ind1v	Evacuation plan (IZhO18_plan)	C++11	100 / 100	803 ms	43636 KiB

plan

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
const int L = 20;

struct dsu {
  int lab[N];
  
  dsu() {
    memset(lab, -1, sizeof(lab));
  }
  
  void reset() {
    memset(lab, -1, sizeof(lab));
  }
  
  int find(int u) {
    return lab[u] < 0 ? u : lab[u] = find(lab[u]);
  }
  
  bool merge(int u, int v) {
    if ((u = find(u)) == (v = find(v))) {
      return false;
    }
    if (lab[u] > lab[v]) {
      swap(u, v);
    }
    lab[u] += lab[v];
    lab[v] = u;
    return true;
  }
};

int n, m;
vector<pair<int, int>> adj[N];
int k;
vector<int> g;
int q;
int s[N], t[N];
int l[N], r[N], ans[N], ord[N];
long long d[N];
vector<int> cand[N];
dsu ds;

void dijkstra() {
  memset(d, 0x3f, sizeof(d));
  priority_queue<pair<long long, int>> pq;
  for (int i = 1; i <= k; i++) {
    d[g[i]] = 0;
    pq.push({-d[g[i]], g[i]});
  }
  while (!pq.empty()) {
    long long cd = -pq.top().first;
    int u = pq.top().second;
    pq.pop();
    if (cd != d[u]) {
      continue;
    }
    for (auto e : adj[u]) {
      if (d[e.first] > d[u] + e.second) {
        d[e.first] = d[u] + e.second;
        pq.push({-d[e.first], e.first});
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int a, b, w;
    cin >> a >> b >> w;
    adj[a].emplace_back(b, w);
    adj[b].emplace_back(a, w);
  }
  cin >> k;
  g.resize(k + 1);
  for (int i = 1; i <= k; i++) {
    cin >> g[i];
  }
  cin >> q;
  for (int i = 1; i <= q; i++) {
    cin >> s[i] >> t[i];
  }
  dijkstra();
  vector<pair<long long, int>> dd(n + 1);
  for (int i = 1; i <= n; i++) {
    dd[i] = {d[i], i};
  }
  sort(dd.begin() + 1, dd.end());
  for (int i = 1; i <= n; i++) {
    ord[dd[i].second] = i;
  }
  for (int i = 1; i <= q; i++) {
    l[i] = 1;
    r[i] = n;
  }
  for (int ite = 1; ite <= L; ite++) {
    ds.reset();
    for (int i = 1; i <= n; i++) {
      cand[i].clear();
    }
    for (int i = 1; i <= q; i++) {
      if (l[i] > r[i]) {
        continue;
      }
      cand[(l[i] + r[i]) >> 1].emplace_back(i);
    }
    for (int i = n; i >= 1; i--) {
      for (auto e : adj[dd[i].second]) {
        if (ord[e.first] >= i) {
          ds.merge(dd[i].second, e.first);
        }
      }
      for (auto qq : cand[i]) {
        if (ds.find(s[qq]) == ds.find(t[qq])) {
          ans[qq] = i;
          l[qq] = i + 1;
        } else {
          r[qq] = i - 1;
        }
      }
    }
  }
  for (int i = 1; i <= q; i++) {
    cout << dd[ans[i]].first << '\n';
  }
  return 0;
}

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