Submission #653145

#	Time	Username	Problem	Language	Result	Execution time	Memory
653145		pauloamed	Evacuation plan (IZhO18_plan)	C++14	100 / 100	804 ms	48856 KiB

plan

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

const int MAXN = 200000;

int dang[MAXN];

struct DSU{
  int sizes[MAXN];
  int parents[MAXN];
  int d[MAXN];
  
  int numComponents;
  stack<pair<int,int>> lastPar, lastSize, lastDang;
  vector<int> checkpoints;

  DSU(int n=0){
    for(int i = 0; i < n; ++i){
      sizes[i] = 1;
      parents[i] = i;
      d[i] = dang[i];
    }
    checkpoints.push_back(0);
    numComponents = n;
  }

  int find(int current){
    int newRoot = current;
    while(newRoot != parents[newRoot]) newRoot = parents[newRoot];
    return newRoot;
  }

  void onion(int a, int b){
    a = find(a); b = find(b);
    if(a == b) return;
    if(sizes[a] < sizes[b]) swap(a,b);

    checkpoints.back()++;
    lastSize.push({a, sizes[a]});
    lastPar.push({b, parents[b]});
    lastDang.push({a, d[a]});
    numComponents--;

    d[a] = min(d[a], d[b]);
    sizes[a] += sizes[b];
    parents[b] = a;
  }

  void check(){ checkpoints.push_back(0); }

  void rollback(){
    int x = checkpoints.back();
    numComponents += x;
    while (x--) {
      sizes[lastSize.top().first] = lastSize.top().second; lastSize.pop();
      parents[lastPar.top().first] = lastPar.top().second; lastPar.pop();
      d[lastDang.top().first] = lastDang.top().second; lastDang.pop();
    }
    checkpoints.pop_back();
  }
};

pair<int,int> qrs[MAXN];
int ans[MAXN];
int evs[MAXN];

vector<pair<int,int>> v[MAXN];

DSU dsu;

void solve(int L, int R, vector<int> on){
  if(L == R || on.empty()){
    for(auto q_i : on) ans[q_i] = L;
  }else{
    int mid = (L + R) / 2;

    int min_dang = dang[evs[mid]];

    // cout << L << " " << R << " " << min_dang << endl;

    dsu.check();
    for(int i = L; i <= mid; ++i){
      for(auto [x, ec] : v[evs[i]]) if(dang[x] >= min_dang){
        // cout << "adding " << x+1 << " " << evs[i]+1 << "\n";
        dsu.onion(x, evs[i]);
      }
    }

    vector<int> done, undone;
    for(auto q_i : on){
      auto [a, b] = qrs[q_i];
      if(dsu.find(a) != dsu.find(b)){
        undone.push_back(q_i);
      }else done.push_back(q_i);
    }
    
    solve(mid + 1, R, undone);
    dsu.rollback();
    solve(L, mid, done);
  }
}

int32_t main(){
  cin.tie(NULL)->sync_with_stdio(false);
  int n, m; cin >> n >> m;

  for(int i = 0; i < n; ++i) dang[i] = INT_MAX;

  for(int i = 0; i < m; ++i){
    int a, b, c; cin >> a >> b >> c;
    a--; b--;
    v[a].push_back({b, c});
    v[b].push_back({a, c});
  }

  struct Node{
    int x, cost;
    bool operator<(const Node &a) const{
      return cost > a.cost;
    }
  };
  priority_queue<Node> pq;

  int k; cin >> k;
  for(int i = 0; i < k; ++i){
    int x; cin >> x; x--;
    pq.push({x, dang[x] = 0});
  }

  while(pq.size()){
    auto [x, cost] = pq.top();
    pq.pop();

    if(cost > dang[x]) continue;
    for(auto [y, ec] : v[x]){
      if(dang[y] > cost + ec){
        pq.push({y, dang[y] = cost + ec});
      }
    }
  }

  dsu = DSU(n);

  int q; cin >> q;
  for(int i = 0; i < q; ++i){
    cin >> qrs[i].first >> qrs[i].second;
    qrs[i].first--;
    qrs[i].second--;
  }

  for(int i = 0; i < n; ++i) evs[i] = i;
  sort(evs, evs + n, [&](int a, int b){
    return dang[a] > dang[b];
  });

  vector<int> qq;
  for(int i = 0; i < q; ++i) qq.push_back(i);
  solve(0, n - 1, qq);

  // for(int i = 0; i < n; ++i){
  //   cout << evs[i]+1 << " " << dang[evs[i]] << "\n";
  // }

  for(int i = 0; i < q; ++i){
    cout << dang[evs[ans[i]]] << "\n";
  }

}

Compilation message (stderr)

plan.cpp: In function 'void solve(int, int, std::vector<int>)':
plan.cpp:83:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |       for(auto [x, ec] : v[evs[i]]) if(dang[x] >= min_dang){
      |                ^
plan.cpp:91:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   91 |       auto [a, b] = qrs[q_i];
      |            ^
plan.cpp: In function 'int32_t main()':
plan.cpp:131:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  131 |     auto [x, cost] = pq.top();
      |          ^
plan.cpp:135:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  135 |     for(auto [y, ec] : v[x]){
      |              ^

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