Submission #570141

#	Time	Username	Problem	Language	Result	Execution time	Memory
570141		SSRS	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1685 ms	37584 KiB

plan

#include <bits/stdc++.h>
using namespace std;
const int LOG = 17;
const int INF = 1000000000;
struct unionfind{
  vector<int> p;
  unionfind(int N): p(N, -1){
  }
  int root(int x){
    if (p[x] < 0){
      return x;
    } else {
      p[x] = root(p[x]);
      return p[x];
    }
  }
  bool same(int x, int y){
    return root(x) == root(y);
  }
  void unite(int x, int y){
    x = root(x);
    y = root(y);
    if (x != y){
      if (p[x] < p[y]){
        swap(x, y);
      }
      p[y] += p[x];
      p[x] = y;
    }
  }
};
int main(){
  int n, m;
  cin >> n >> m;
  vector<vector<pair<int, int>>> E(n);
  for (int i = 0; i < m; i++){
    int a, b, w;
    cin >> a >> b >> w;
    a--;
    b--;
    E[a].push_back(make_pair(w, b));
    E[b].push_back(make_pair(w, a));
  }
  int k;
  cin >> k;
  vector<int> g(k);
  for (int i = 0; i < k; i++){
    cin >> g[i];
    g[i]--;
  }
  vector<int> d(n, -1);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  for (int i = 0; i < k; i++){
    pq.push(make_pair(0, g[i]));
  }
  while (!pq.empty()){
    int c = pq.top().first;
    int v = pq.top().second;
    pq.pop();
    if (d[v] == -1){
      d[v] = c;
      for (auto P : E[v]){
        int w = P.second;
        if (d[w] == -1){
          pq.push(make_pair(c + P.first, w));
        }
      }
    }
  }
  vector<tuple<int, int, int>> E2;
  for (int i = 0; i < n; i++){
    for (auto P : E[i]){
      int j = P.second;
      if (i < j){
        E2.push_back(make_tuple(min(d[i], d[j]), i, j));
      }
    }
  }
  sort(E2.begin(), E2.end(), greater<tuple<int, int, int>>());
  unionfind UF(n);
  vector<tuple<int, int, int>> E3;
  for (int i = 0; i < m; i++){
    int u = get<1>(E2[i]);
    int v = get<2>(E2[i]);
    if (!UF.same(u, v)){
      UF.unite(u, v);
      int c = get<0>(E2[i]);
      E3.push_back(make_tuple(c, u, v));
    }
  }
  int Q;
  cin >> Q;
  vector<int> s(Q), t(Q);
  for (int i = 0; i < Q; i++){
    cin >> s[i] >> t[i];
    s[i]--;
    t[i]--;
  }
  vector<int> tv(Q, 0);
  vector<int> fv(Q, INF);
  while (true){
    bool ok = true;
    vector<tuple<int, int, int, int>> query;
    for (int i = 0; i < Q; i++){
      if (fv[i] - tv[i] > 1){
        ok = false;
        query.push_back(make_tuple((tv[i] + fv[i]) / 2, 0, i, -1));
      }
    }
    if (ok){
      break;
    }
    for (auto e : E3){
      query.push_back(make_tuple(get<0>(e), 1, get<1>(e), get<2>(e)));
    }
    sort(query.begin(), query.end(), greater<tuple<int, int, int, int>>());
    int cnt = query.size();
    unionfind UF2(n);
    for (int i = 0; i < cnt; i++){
      int x = get<1>(query[i]);
      if (x == 0){
        int id = get<2>(query[i]);
        if (UF2.same(s[id], t[id])){
          tv[id] = (tv[id] + fv[id]) / 2;
        } else {
          fv[id] = (tv[id] + fv[id]) / 2;
        }
      }
      if (x == 1){
        int u = get<2>(query[i]);
        int v = get<3>(query[i]);
        UF2.unite(u, v);
      }
    }
  }
  for (int i = 0; i < Q; i++){
    cout << tv[i] << endl;
  }
}

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