oj.uz

Submission #947249

# Submission time Handle Problem Language Result Execution time Memory
947249 2024-03-15T18:48:07 Z nguyennh Evacuation plan (IZhO18_plan) C++14
22 / 100
 123 ms 31572 KB 
#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 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[MN];
pair<int , int> queries[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));
      }
    }
  }
  int mn = INT_MAX , mx = INT_MIN;
  for ( int i = 1 ; i <= n ; i++ ){
    mn = min(mn , dis[i]);
    mx = max(mx , dis[i]);
  }
  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;
  }
  sort(edge , edge + m);
  DSU dsu;
  for ( int i = 0 ; i < q ; i++ ){
    l[i] = mn;
    r[i] = mx;
  }
  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 = mx ; mid >= mn ; mid-- ){
      while (j >= 0 && edge[j].first >= mid){
        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 << r[i] << el;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7000 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 2 ms 7004 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 2 ms 7000 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 3 ms 7004 KB Output is correct
10 Correct 3 ms 7256 KB Output is correct
11 Correct 3 ms 7004 KB Output is correct
12 Correct 2 ms 7004 KB Output is correct
13 Correct 3 ms 6920 KB Output is correct
14 Correct 3 ms 7000 KB Output is correct
15 Correct 3 ms 7000 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7000 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 2 ms 7004 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 2 ms 7000 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 3 ms 7004 KB Output is correct
10 Correct 3 ms 7256 KB Output is correct
11 Correct 3 ms 7004 KB Output is correct
12 Correct 2 ms 7004 KB Output is correct
13 Correct 3 ms 6920 KB Output is correct
14 Correct 3 ms 7000 KB Output is correct
15 Correct 3 ms 7000 KB Output is correct
16 Correct 123 ms 19272 KB Output is correct
17 Runtime error 122 ms 31572 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 2 ms 6744 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 1 ms 6744 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 2 ms 7000 KB Output is correct
10 Correct 2 ms 6904 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 106 ms 28720 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7000 KB Output is correct
2 Correct 2 ms 7004 KB Output is correct
3 Correct 2 ms 7004 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 2 ms 7000 KB Output is correct
6 Correct 2 ms 7004 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 3 ms 7004 KB Output is correct
10 Correct 3 ms 7256 KB Output is correct
11 Correct 3 ms 7004 KB Output is correct
12 Correct 2 ms 7004 KB Output is correct
13 Correct 3 ms 6920 KB Output is correct
14 Correct 3 ms 7000 KB Output is correct
15 Correct 3 ms 7000 KB Output is correct
16 Correct 123 ms 19272 KB Output is correct
17 Runtime error 122 ms 31572 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -