oj.uz

답안 #947255

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
947255 2024-03-15T19:02:30 Z nguyennh Evacuation plan (IZhO18_plan) C++14
22 / 100
 389 ms 32228 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)1e7);
  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 5208 KB Output is correct
2 Correct 3 ms 5468 KB Output is correct
3 Correct 3 ms 5416 KB Output is correct
4 Correct 2 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 5464 KB Output is correct
9 Correct 14 ms 5980 KB Output is correct
10 Correct 4 ms 5464 KB Output is correct
11 Correct 10 ms 5724 KB Output is correct
12 Correct 4 ms 5284 KB Output is correct
13 Correct 10 ms 5724 KB Output is correct
14 Correct 18 ms 5980 KB Output is correct
15 Correct 11 ms 5724 KB Output is correct

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 3 ms 5468 KB Output is correct
3 Correct 3 ms 5416 KB Output is correct
4 Correct 2 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 5464 KB Output is correct
9 Correct 14 ms 5980 KB Output is correct
10 Correct 4 ms 5464 KB Output is correct
11 Correct 10 ms 5724 KB Output is correct
12 Correct 4 ms 5284 KB Output is correct
13 Correct 10 ms 5724 KB Output is correct
14 Correct 18 ms 5980 KB Output is correct
15 Correct 11 ms 5724 KB Output is correct
16 Correct 182 ms 18184 KB Output is correct
17 Correct 344 ms 32144 KB Output is correct
18 Correct 31 ms 7516 KB Output is correct
19 Correct 99 ms 16900 KB Output is correct
20 Correct 389 ms 32228 KB Output is correct
21 Correct 227 ms 21900 KB Output is correct
22 Runtime error 33 ms 17244 KB Execution killed with signal 6
23 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5212 KB Output is correct
2 Correct 3 ms 5364 KB Output is correct
3 Correct 2 ms 5276 KB Output is correct
4 Correct 2 ms 5208 KB Output is correct
5 Correct 1 ms 5212 KB Output is correct
6 Correct 1 ms 5208 KB Output is correct
7 Correct 1 ms 5212 KB Output is correct
8 Correct 2 ms 5268 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 136 ms 15664 KB Output is correct
2 Correct 330 ms 25348 KB Output is correct
3 Correct 279 ms 25288 KB Output is correct
4 Runtime error 37 ms 17232 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 3 ms 5468 KB Output is correct
3 Correct 3 ms 5416 KB Output is correct
4 Correct 2 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 5464 KB Output is correct
9 Correct 14 ms 5980 KB Output is correct
10 Correct 4 ms 5464 KB Output is correct
11 Correct 10 ms 5724 KB Output is correct
12 Correct 4 ms 5284 KB Output is correct
13 Correct 10 ms 5724 KB Output is correct
14 Correct 18 ms 5980 KB Output is correct
15 Correct 11 ms 5724 KB Output is correct
16 Correct 182 ms 18184 KB Output is correct
17 Correct 344 ms 32144 KB Output is correct
18 Correct 31 ms 7516 KB Output is correct
19 Correct 99 ms 16900 KB Output is correct
20 Correct 389 ms 32228 KB Output is correct
21 Correct 227 ms 21900 KB Output is correct
22 Runtime error 33 ms 17244 KB Execution killed with signal 6
23 Halted 0 ms 0 KB -