oj.uz

답안 #947252

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
947252 2024-03-15T18:54:32 Z nguyennh Evacuation plan (IZhO18_plan) C++14
22 / 100
 2566 ms 524288 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]);
  }
  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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5212 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 3 ms 5212 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 3 ms 5212 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 12 ms 5772 KB Output is correct
12 Correct 3 ms 5212 KB Output is correct
13 Correct 9 ms 5724 KB Output is correct
14 Correct 17 ms 6144 KB Output is correct
15 Correct 11 ms 5724 KB Output is correct

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5212 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 3 ms 5212 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 3 ms 5212 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 12 ms 5772 KB Output is correct
12 Correct 3 ms 5212 KB Output is correct
13 Correct 9 ms 5724 KB Output is correct
14 Correct 17 ms 6144 KB Output is correct
15 Correct 11 ms 5724 KB Output is correct
16 Correct 179 ms 18352 KB Output is correct
17 Correct 346 ms 32200 KB Output is correct
18 Correct 33 ms 7660 KB Output is correct
19 Correct 87 ms 16968 KB Output is correct
20 Correct 357 ms 32204 KB Output is correct
21 Correct 204 ms 21880 KB Output is correct
22 Runtime error 2566 ms 524288 KB Execution killed with signal 9
23 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5208 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 2 ms 5212 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 2 ms 5200 KB Output is correct
7 Correct 1 ms 5212 KB Output is correct
8 Correct 2 ms 5212 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 15512 KB Output is correct
2 Correct 274 ms 25428 KB Output is correct
3 Correct 297 ms 25288 KB Output is correct
4 Runtime error 2562 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5212 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 3 ms 5212 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 5212 KB Output is correct
7 Correct 3 ms 5212 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 12 ms 5772 KB Output is correct
12 Correct 3 ms 5212 KB Output is correct
13 Correct 9 ms 5724 KB Output is correct
14 Correct 17 ms 6144 KB Output is correct
15 Correct 11 ms 5724 KB Output is correct
16 Correct 179 ms 18352 KB Output is correct
17 Correct 346 ms 32200 KB Output is correct
18 Correct 33 ms 7660 KB Output is correct
19 Correct 87 ms 16968 KB Output is correct
20 Correct 357 ms 32204 KB Output is correct
21 Correct 204 ms 21880 KB Output is correct
22 Runtime error 2566 ms 524288 KB Execution killed with signal 9
23 Halted 0 ms 0 KB -