Submission #570142

#	Time	Username	Problem	Language	Result	Execution time	Memory
570142		SSRS	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1164 ms	50828 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<vector<pair<int, int>>> E3(n);
  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[u].push_back(make_pair(c, v));
      E3[v].push_back(make_pair(c, u));
    }
  }
  vector<int> p(n, -1);
  vector<int> a(n);
  vector<vector<int>> c(n);
  vector<int> d2(n, 0);
  queue<int> q;
  q.push(0);
  while (!q.empty()){
    int v = q.front();
    q.pop();
    for (auto P : E3[v]){
      int w = P.second;
      if (w != p[v]){
        p[w] = v;
        a[w] = P.first;
        c[v].push_back(w);
        d2[w] = d2[v] + 1;
        q.push(w);
      }
    }
  }
  vector<vector<int>> pp(LOG, vector<int>(n, -1));
  vector<vector<int>> mn(LOG, vector<int>(n, INF));
  for (int i = 0; i < n; i++){
    pp[0][i] = p[i];
    mn[0][i] = a[i];
  }
  for (int i = 0; i < LOG - 1; i++){
    for (int j = 0; j < n; j++){
      if (pp[i][j] != -1){
        pp[i + 1][j] = pp[i][pp[i][j]];
        if (pp[i + 1][j] != -1){
          mn[i + 1][j] = min(mn[i][j], mn[i][pp[i][j]]);
        }
      }
    }
  }
  int Q;
  cin >> Q;
  for (int i = 0; i < Q; i++){
    int s, t;
    cin >> s >> t;
    s--;
    t--;
    int ans = INF;
    if (d2[s] > d2[t]){
      swap(s, t);
    }
    for (int j = 0; j < LOG; j++){
      if (((d2[t] - d2[s]) >> j & 1) == 1){
        ans = min(ans, mn[j][t]);
        t = pp[j][t];
      }
    }
    if (s != t){
      for (int j = LOG - 1; j >= 0; j--){
        if (pp[j][s] != pp[j][t]){
          ans = min(ans, mn[j][s]);
          ans = min(ans, mn[j][t]);
          s = pp[j][s];
          t = pp[j][t];
        }
      }
      ans = min(ans, mn[0][s]);
      ans = min(ans, mn[0][t]);
    }
    cout << ans << endl;
  }
}

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