oj.uz

Submission #947254

# Submission time Handle Problem Language Result Execution time Memory
947254 2024-03-15T19:01:59 Z nguyennh Evacuation plan (IZhO18_plan) C++14
22 / 100
 382 ms 32200 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 N = 5e5 + 5;
const int inf = 1e9;

int dis[MN] , l[MN] , r[MN];
vector<pair<int , int>> adj[MN];
map<int , vector<int>> candidates;
pair<int , pair<int , int>> edge[N];
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]);
  }
  assert(mx <= (int)1e6);
  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: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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5212 KB Output is correct
2 Correct 3 ms 5256 KB Output is correct
3 Correct 3 ms 5208 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 3 ms 5208 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 3 ms 5208 KB Output is correct
8 Correct 2 ms 5212 KB Output is correct
9 Correct 14 ms 5980 KB Output is correct
10 Correct 4 ms 5464 KB Output is correct
11 Correct 11 ms 5724 KB Output is correct
12 Correct 3 ms 5208 KB Output is correct
13 Correct 8 ms 5720 KB Output is correct
14 Correct 17 ms 5980 KB Output is correct
15 Correct 11 ms 5724 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5212 KB Output is correct
2 Correct 3 ms 5256 KB Output is correct
3 Correct 3 ms 5208 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 3 ms 5208 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 3 ms 5208 KB Output is correct
8 Correct 2 ms 5212 KB Output is correct
9 Correct 14 ms 5980 KB Output is correct
10 Correct 4 ms 5464 KB Output is correct
11 Correct 11 ms 5724 KB Output is correct
12 Correct 3 ms 5208 KB Output is correct
13 Correct 8 ms 5720 KB Output is correct
14 Correct 17 ms 5980 KB Output is correct
15 Correct 11 ms 5724 KB Output is correct
16 Correct 184 ms 18316 KB Output is correct
17 Correct 382 ms 32176 KB Output is correct
18 Correct 33 ms 7512 KB Output is correct
19 Correct 90 ms 16968 KB Output is correct
20 Correct 356 ms 32200 KB Output is correct
21 Correct 182 ms 21968 KB Output is correct
22 Runtime error 33 ms 17236 KB Execution killed with signal 6
23 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 1 ms 5212 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 1 ms 5212 KB Output is correct
7 Correct 2 ms 5208 KB Output is correct
8 Correct 2 ms 5208 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 1 ms 5208 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 15568 KB Output is correct
2 Correct 267 ms 25288 KB Output is correct
3 Correct 270 ms 25288 KB Output is correct
4 Runtime error 32 ms 17232 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5212 KB Output is correct
2 Correct 3 ms 5256 KB Output is correct
3 Correct 3 ms 5208 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 3 ms 5208 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 3 ms 5208 KB Output is correct
8 Correct 2 ms 5212 KB Output is correct
9 Correct 14 ms 5980 KB Output is correct
10 Correct 4 ms 5464 KB Output is correct
11 Correct 11 ms 5724 KB Output is correct
12 Correct 3 ms 5208 KB Output is correct
13 Correct 8 ms 5720 KB Output is correct
14 Correct 17 ms 5980 KB Output is correct
15 Correct 11 ms 5724 KB Output is correct
16 Correct 184 ms 18316 KB Output is correct
17 Correct 382 ms 32176 KB Output is correct
18 Correct 33 ms 7512 KB Output is correct
19 Correct 90 ms 16968 KB Output is correct
20 Correct 356 ms 32200 KB Output is correct
21 Correct 182 ms 21968 KB Output is correct
22 Runtime error 33 ms 17236 KB Execution killed with signal 6
23 Halted 0 ms 0 KB -