Submission #529310

#	Time	Username	Problem	Language	Result	Execution time	Memory
529310		Alex_tz307	Evacuation plan (IZhO18_plan)	C++17	100 / 100	709 ms	38460 KiB

plan

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

struct queryS {
  int s, t, index, sol;

  void read() {
    cin >> s >> t;
  }

  bool operator < (const queryS &rhs) const {
    return sol > rhs.sol;
  }
};

struct DSU {
  vector<int> p, sz;

  DSU(int n) {
    p.resize(n + 1);
    iota(p.begin(), p.end(), 0);
    sz.assign(n + 1, 1);
  }

  int root(int x) {
    if (x == p[x]) {
      return x;
    }
    return p[x] = root(p[x]);
  }

  bool unite(int u, int v) {
    int x = root(u), y = root(v);
    if (x == y) {
      return false;
    }
    if (sz[y] < sz[x]) {
      swap(x, y);
    }
    p[x] = y;
    sz[y] += sz[x];
    return true;
  }
};

/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

void testCase() {
  int n, m;
  cin >> n >> m;
  vector<tuple<int, int, int>> edges(m);
  vector<vector<pair<int, int>>> g(n + 1);
  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);
    edges[i] = {-1, u, v};
  }
  int k;
  cin >> k;
  vector<int> dp(n + 1, INF);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  for (int i = 0; i < k; ++i) {
    int x;
    cin >> x;
    dp[x] = 0;
    pq.emplace(0, x);
  }
  while (!pq.empty()) {
    int d, u;
    tie(d, u) = pq.top();
    pq.pop();
    if (d != dp[u]) {
      continue;
    }
    for (auto it : g[u]) {
      int v, w;
      tie(v, w) = it;
      if (dp[v] > d + w) {
        dp[v] = d + w;
        pq.emplace(dp[v], v);
      }
    }
  }
  for (int i = 0; i < m; ++i) {
    int aux, u, v;
    tie(aux, u, v) = edges[i];
    edges[i] = {min(dp[u], dp[v]), u, v};
  }
  edges.emplace_back(-INF, -INF, -INF);
  sort(edges.rbegin(), edges.rend());
  int Q;
  cin >> Q;
  vector<queryS> q(Q);
  for (int i = 0; i < Q; ++i) {
    q[i].read();
    q[i].index = i;
    q[i].sol = 0;
  }
  int step = (1 << 29);
  while (step >= 1) {
    for (int i = 0; i < Q; ++i) {
      q[i].sol += step;
    }
    DSU dsu(n);
    int ptr = 0;
    for (auto it : edges) {
      int w, u, v;
      tie(w, u, v) = it;
      while (ptr < Q && q[ptr].sol > w) {
        if (dsu.root(q[ptr].s) != dsu.root(q[ptr].t)) {
          q[ptr].sol -= step;
        }
        ptr += 1;
      }
      if (w != -INF) {
        dsu.unite(u, v);
      }
    }
    if (step > 1) {
      sort(q.begin(), q.end());
    }
    step /= 2;
  }
  vector<int> sol(Q);
  for (int i = 0; i < Q; ++i) {
    sol[q[i].index] = q[i].sol;
  }
  for (int i = 0; i < Q; ++i) {
    cout << sol[i] << '\n';
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

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