Submission #947260

#	Time	Username	Problem	Language	Result	Execution time	Memory
947260		nguyennh	Evacuation plan (IZhO18_plan)	C++14	100 / 100	408 ms	48628 KiB

plan

#include<bits/stdc++.h>
#define el '\n'
using namespace std ;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());

const int MN = 1e5 + 5;
const int N = 5e5 + 5;
const int inf = 1e9;

int dis[MN] , l[MN] , r[MN];
vector<pair<int , int>> adj[MN];
vector<int> candidates[MN];
pair<int , pair<int , int>> edge[N];
pair<int , int> queries[MN] , cur[MN];

struct DSU{
  vector<int> par , sz;
  int n;
  
  void init(int n){
    this -> n = n;
    par.resize(n + 5);
    sz.resize(n + 5 , 1);
    for ( int i = 1 ; i <= n ; i++ ) par[i] = i;
  }
  
  int find_set(int v){
    return v == par[v] ? v : par[v] = find_set(par[v]);
  }
  
  void unite(int r , int s){
    r = find_set(r) , s = find_set(s);
    if (r != s){
      if (sz[r] < sz[s]) swap(r , s);
      par[s] = r;
      sz[r] += sz[s];
    }
  }
  
  bool same_set(int u , int v){
    return find_set(u) == find_set(v);
  }
};

int32_t main (){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n , m;
  cin >> n >> m;
  for ( int i = 0 ; i < m ; i++ ){
    int u , v , w;
    cin >> u >> v >> w;
    adj[u].push_back(make_pair(v , w));
    adj[v].push_back(make_pair(u , w));
    edge[i].second = make_pair(u , v);
  }
  priority_queue<pair<int , int> , vector<pair<int , int>> , greater<pair<int , int>>> pq;
  for ( int i = 1 ; i <= n ; i++ ) dis[i] = inf; 
  int k;
  cin >> k;
  for ( int i = 1 ; i <= k ; i++ ){
    int x;
    cin >> x;
    dis[x] = 0;
    pq.push(make_pair(0 , x));
  }
  while (!pq.empty()){
    auto [d , u] = pq.top();
    pq.pop();
    if (d != dis[u]) continue;
    for ( auto [v , w] : adj[u] ){
      if (dis[v] > dis[u] + w){
        dis[v] = dis[u] + w;
        pq.push(make_pair(dis[v] , v));
      }
    }
  }
  for ( int i = 0 ; i < m ; i++ ) edge[i].first = min(dis[edge[i].second.first] , dis[edge[i].second.second]);
  int q;
  cin >> q;
  for ( int i = 0 ; i < q ; i++ ){
    cin >> queries[i].first >> queries[i].second;
  }
  for ( int i = 1 ; i <= n ; i++ ) cur[i] = make_pair(dis[i] , i);
  sort(cur + 1 , cur + n + 1);
  sort(edge , edge + m);
  DSU dsu;
  for ( int i = 0 ; i < q ; i++ ){
    l[i] = 1;
    r[i] = n;
  }
  while (1){
    bool any = false;
    for ( int i = 0 ; i < q ; i++ ){
      if (l[i] <= r[i]){
        int mid = (l[i] + r[i]) / 2;
        candidates[mid].push_back(i);
        any = true;
      }
    }
    if (!any) break;
    dsu.init(n);
    int j = m - 1;
    for ( int mid = n ; mid >= 1 ; mid-- ){
      while (j >= 0 && edge[j].first >= cur[mid].first){
        dsu.unite(edge[j].second.first , edge[j].second.second);
        j--;
      }
      for ( auto x : candidates[mid] ){
        if (dsu.same_set(queries[x].first , queries[x].second)){
          l[x] = mid + 1;
        }
        else r[x] = mid - 1;
      } 
      candidates[mid].clear();
    }
  }
  for ( int i = 0 ; i < q ; i++ ) cout << cur[r[i]].first << el;
}

Compilation message (stderr)

plan.cpp: In function 'int32_t main()':
plan.cpp:69:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |     auto [d , u] = pq.top();
      |          ^
plan.cpp:72:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |     for ( auto [v , w] : adj[u] ){
      |                ^

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