oj.uz

답안 #947251

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
947251 2024-03-15T18:51:01 Z nguyennh Evacuation plan (IZhO18_plan) C++14
22 / 100
 353 ms 44368 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];
vector<int> candidates[N];
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 4 ms 16728 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 3 ms 16728 KB Output is correct
9 Correct 5 ms 16988 KB Output is correct
10 Correct 5 ms 16988 KB Output is correct
11 Correct 5 ms 16988 KB Output is correct
12 Correct 4 ms 16940 KB Output is correct
13 Correct 5 ms 16892 KB Output is correct
14 Correct 5 ms 16984 KB Output is correct
15 Correct 5 ms 16988 KB Output is correct

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 3 ms 16728 KB Output is correct
9 Correct 5 ms 16988 KB Output is correct
10 Correct 5 ms 16988 KB Output is correct
11 Correct 5 ms 16988 KB Output is correct
12 Correct 4 ms 16940 KB Output is correct
13 Correct 5 ms 16892 KB Output is correct
14 Correct 5 ms 16984 KB Output is correct
15 Correct 5 ms 16988 KB Output is correct
16 Correct 120 ms 29332 KB Output is correct
17 Correct 333 ms 43984 KB Output is correct
18 Correct 28 ms 19024 KB Output is correct
19 Correct 82 ms 28492 KB Output is correct
20 Correct 353 ms 44368 KB Output is correct
21 Correct 165 ms 33272 KB Output is correct
22 Runtime error 59 ms 42836 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

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

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 27180 KB Output is correct
2 Correct 272 ms 37056 KB Output is correct
3 Correct 269 ms 37064 KB Output is correct
4 Runtime error 53 ms 41060 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 16732 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 3 ms 16732 KB Output is correct
8 Correct 3 ms 16728 KB Output is correct
9 Correct 5 ms 16988 KB Output is correct
10 Correct 5 ms 16988 KB Output is correct
11 Correct 5 ms 16988 KB Output is correct
12 Correct 4 ms 16940 KB Output is correct
13 Correct 5 ms 16892 KB Output is correct
14 Correct 5 ms 16984 KB Output is correct
15 Correct 5 ms 16988 KB Output is correct
16 Correct 120 ms 29332 KB Output is correct
17 Correct 333 ms 43984 KB Output is correct
18 Correct 28 ms 19024 KB Output is correct
19 Correct 82 ms 28492 KB Output is correct
20 Correct 353 ms 44368 KB Output is correct
21 Correct 165 ms 33272 KB Output is correct
22 Runtime error 59 ms 42836 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -