Submission #854075

#	Time	Username	Problem	Language	Result	Execution time	Memory
854075		NeroZein	Evacuation plan (IZhO18_plan)	C++17	100 / 100	573 ms	31784 KiB

plan

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

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int N = 1e5 + 5;
const int INF = 1e9; 

int n, m;
int cost[N]; 
bool added[N];
int p[N], sz[N];
vector<pair<int, int>> g[N]; 

void init_dsu() {
  for (int i = 1; i <= n; ++i) {
    sz[i] = 1;
    p[i] = i; 
  }
}

int get(int v) {
  return p[v] = (p[v] == v ? v : get(p[v])); 
}

void unite(int u, int v) {
  u = get(u); v = get(v);
  if (u == v) {
    return;
  }
  if (sz[u] > sz[v]) {
    swap(u, v);
  }
  sz[v] += sz[u];
  p[u] = v; 
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w); 
  }
  priority_queue<pair<int, int>> pq;
  fill(cost, cost + N, INF); 
  int k;
  cin >> k;
  for (int i = 0; i < k; ++i) {
    int v;
    cin >> v;
    cost[v] = 0; 
    pq.emplace(0, v); 
  }
  while (!pq.empty()) {
    auto [c, v] = pq.top();
    pq.pop();
    c = -c;
    if (c != cost[v]) {
      continue;
    }
    for (auto [u, w] : g[v]) {
      if (cost[u] > c + w) {
        cost[u] = c + w;
        pq.emplace(-cost[u], u); 
      }
    }
  }
  int q;
  cin >> q;
  vector<array<int, 6>> qs(q);
  for (int i = 0; i < q; ++i) {
    int u, v;
    cin >> u >> v;
    qs[i][1] = 0;
    qs[i][2] = INF;
    qs[i][3] = i;
    qs[i][4] = u;
    qs[i][5] = v; 
  }
  vector<int> ids(n);
  iota(ids.begin(), ids.end(), 1); 
  sort(ids.begin(), ids.end(), [&](int i, int j) {
    return cost[i] > cost[j];
  });
  while (true) {
    init_dsu(); 
    bool changed = false;
    for (int i = 0; i < q; ++i) {
      if (qs[i][1] != qs[i][2]) {
        changed = true; 
      }
      qs[i][0] = (qs[i][1] + qs[i][2] + 1) / 2; 
      //deb(qs[i]); cout << '\n';
    }
    if (!changed) {
      break; 
    }
    sort(qs.begin(), qs.end(), [&](array<int, 6> i, array<int, 6> j) {
      return i[0] > j[0];
    });
    int ptr = 0;
    for (int i = 0; i < q; ++i) {
      auto& [mid, l, r, qid, qu, qv] = qs[i];
      while (ptr < n && cost[ids[ptr]] >= mid) {
        for (auto [u, w] : g[ids[ptr]]) {
          if (added[u]) {
            unite(u, ids[ptr]); 
          }
        }
        added[ids[ptr]] = true; 
        ptr++;
      }
      if (get(qu) == get(qv)) {
        l = mid;
      } else {
        r = mid - 1; 
      }
    }
    for (int i = 0; i < ptr; ++i) {
      added[ids[i]] = false;
    }
  }
  sort(qs.begin(), qs.end(), [](array<int, 6> i, array<int, 6> j) {
    return i[3] < j[3];
  });
  for (int i = 0; i < q; ++i) {
    cout << qs[i][1] << '\n';
  }
  return 0;
}

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