oj.uz

답안 #947256

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
947256 2024-03-15T19:02:56 Z nguyennh Evacuation plan (IZhO18_plan) C++14
22 / 100
 2498 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]);
  }
  assert(mx <= (int)1e8);
  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 2 ms 5212 KB Output is correct
2 Correct 3 ms 5468 KB Output is correct
3 Correct 3 ms 5208 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 6028 KB Output is correct
10 Correct 4 ms 5468 KB Output is correct
11 Correct 10 ms 5852 KB Output is correct
12 Correct 3 ms 5464 KB Output is correct
13 Correct 8 ms 5660 KB Output is correct
14 Correct 17 ms 5976 KB Output is correct
15 Correct 11 ms 5724 KB Output is correct

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 3 ms 5468 KB Output is correct
3 Correct 3 ms 5208 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 6028 KB Output is correct
10 Correct 4 ms 5468 KB Output is correct
11 Correct 10 ms 5852 KB Output is correct
12 Correct 3 ms 5464 KB Output is correct
13 Correct 8 ms 5660 KB Output is correct
14 Correct 17 ms 5976 KB Output is correct
15 Correct 11 ms 5724 KB Output is correct
16 Correct 203 ms 18252 KB Output is correct
17 Correct 349 ms 32216 KB Output is correct
18 Correct 32 ms 7516 KB Output is correct
19 Correct 87 ms 16728 KB Output is correct
20 Correct 335 ms 32152 KB Output is correct
21 Correct 198 ms 22108 KB Output is correct
22 Runtime error 2468 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 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5208 KB Output is correct
4 Correct 1 ms 5212 KB Output is correct
5 Correct 2 ms 5212 KB Output is correct
6 Correct 2 ms 5212 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 5208 KB Output is correct

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 15708 KB Output is correct
2 Correct 304 ms 25264 KB Output is correct
3 Correct 291 ms 25356 KB Output is correct
4 Runtime error 2498 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 3 ms 5468 KB Output is correct
3 Correct 3 ms 5208 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 6028 KB Output is correct
10 Correct 4 ms 5468 KB Output is correct
11 Correct 10 ms 5852 KB Output is correct
12 Correct 3 ms 5464 KB Output is correct
13 Correct 8 ms 5660 KB Output is correct
14 Correct 17 ms 5976 KB Output is correct
15 Correct 11 ms 5724 KB Output is correct
16 Correct 203 ms 18252 KB Output is correct
17 Correct 349 ms 32216 KB Output is correct
18 Correct 32 ms 7516 KB Output is correct
19 Correct 87 ms 16728 KB Output is correct
20 Correct 335 ms 32152 KB Output is correct
21 Correct 198 ms 22108 KB Output is correct
22 Runtime error 2468 ms 524288 KB Execution killed with signal 9
23 Halted 0 ms 0 KB -