oj.uz

Submission #947260

# Submission time Handle Problem Language Result Execution time Memory
947260 2024-03-15T19:17:56 Z nguyennh Evacuation plan (IZhO18_plan) C++14
100 / 100
 408 ms 48628 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[MN];
pair<int , pair<int , int>> edge[N];
pair<int , int> queries[MN] , cur[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));
      }
    }
  }
  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;
  }
  for ( int i = 1 ; i <= n ; i++ ) cur[i] = make_pair(dis[i] , i);
  sort(cur + 1 , cur + n + 1);
  sort(edge , edge + m);
  DSU dsu;
  for ( int i = 0 ; i < q ; i++ ){
    l[i] = 1;
    r[i] = n;
  }
  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 = n ; mid >= 1 ; mid-- ){
      while (j >= 0 && edge[j].first >= cur[mid].first){
        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 << cur[r[i]].first << 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 1 ms 8536 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 3 ms 8796 KB Output is correct
6 Correct 3 ms 8796 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8632 KB Output is correct
9 Correct 3 ms 9048 KB Output is correct
10 Correct 2 ms 8796 KB Output is correct
11 Correct 3 ms 8796 KB Output is correct
12 Correct 2 ms 8796 KB Output is correct
13 Correct 3 ms 8796 KB Output is correct
14 Correct 3 ms 8796 KB Output is correct
15 Correct 3 ms 8796 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 3 ms 8796 KB Output is correct
6 Correct 3 ms 8796 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8632 KB Output is correct
9 Correct 3 ms 9048 KB Output is correct
10 Correct 2 ms 8796 KB Output is correct
11 Correct 3 ms 8796 KB Output is correct
12 Correct 2 ms 8796 KB Output is correct
13 Correct 3 ms 8796 KB Output is correct
14 Correct 3 ms 8796 KB Output is correct
15 Correct 3 ms 8796 KB Output is correct
16 Correct 153 ms 25256 KB Output is correct
17 Correct 342 ms 39100 KB Output is correct
18 Correct 28 ms 10916 KB Output is correct
19 Correct 96 ms 24712 KB Output is correct
20 Correct 359 ms 38864 KB Output is correct
21 Correct 220 ms 27148 KB Output is correct
22 Correct 130 ms 26572 KB Output is correct
23 Correct 383 ms 48360 KB Output is correct
24 Correct 384 ms 48516 KB Output is correct
25 Correct 373 ms 48076 KB Output is correct
26 Correct 98 ms 27452 KB Output is correct
27 Correct 96 ms 27464 KB Output is correct
28 Correct 99 ms 27004 KB Output is correct
29 Correct 98 ms 27208 KB Output is correct
30 Correct 95 ms 27720 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 19156 KB Output is correct
2 Correct 298 ms 28876 KB Output is correct
3 Correct 325 ms 29132 KB Output is correct
4 Correct 73 ms 15356 KB Output is correct
5 Correct 322 ms 37208 KB Output is correct
6 Correct 312 ms 37072 KB Output is correct
7 Correct 292 ms 37060 KB Output is correct
8 Correct 303 ms 37188 KB Output is correct
9 Correct 315 ms 37000 KB Output is correct
10 Correct 315 ms 37184 KB Output is correct
11 Correct 292 ms 37328 KB Output is correct
12 Correct 349 ms 37176 KB Output is correct
13 Correct 305 ms 37080 KB Output is correct
14 Correct 326 ms 37072 KB Output is correct
15 Correct 299 ms 37584 KB Output is correct
16 Correct 296 ms 37064 KB Output is correct
17 Correct 309 ms 37068 KB Output is correct
18 Correct 337 ms 37352 KB Output is correct
19 Correct 57 ms 16724 KB Output is correct
20 Correct 308 ms 37008 KB Output is correct
21 Correct 301 ms 37232 KB Output is correct
22 Correct 64 ms 18280 KB Output is correct
23 Correct 80 ms 17220 KB Output is correct
24 Correct 82 ms 18248 KB Output is correct
25 Correct 63 ms 18240 KB Output is correct
26 Correct 81 ms 17488 KB Output is correct
27 Correct 66 ms 16836 KB Output is correct
28 Correct 64 ms 18248 KB Output is correct
29 Correct 62 ms 16724 KB Output is correct
30 Correct 65 ms 18504 KB Output is correct
31 Correct 63 ms 16596 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 3 ms 8796 KB Output is correct
6 Correct 3 ms 8796 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8632 KB Output is correct
9 Correct 3 ms 9048 KB Output is correct
10 Correct 2 ms 8796 KB Output is correct
11 Correct 3 ms 8796 KB Output is correct
12 Correct 2 ms 8796 KB Output is correct
13 Correct 3 ms 8796 KB Output is correct
14 Correct 3 ms 8796 KB Output is correct
15 Correct 3 ms 8796 KB Output is correct
16 Correct 153 ms 25256 KB Output is correct
17 Correct 342 ms 39100 KB Output is correct
18 Correct 28 ms 10916 KB Output is correct
19 Correct 96 ms 24712 KB Output is correct
20 Correct 359 ms 38864 KB Output is correct
21 Correct 220 ms 27148 KB Output is correct
22 Correct 130 ms 26572 KB Output is correct
23 Correct 383 ms 48360 KB Output is correct
24 Correct 384 ms 48516 KB Output is correct
25 Correct 373 ms 48076 KB Output is correct
26 Correct 98 ms 27452 KB Output is correct
27 Correct 96 ms 27464 KB Output is correct
28 Correct 99 ms 27004 KB Output is correct
29 Correct 98 ms 27208 KB Output is correct
30 Correct 95 ms 27720 KB Output is correct
31 Correct 2 ms 8536 KB Output is correct
32 Correct 2 ms 8536 KB Output is correct
33 Correct 2 ms 8536 KB Output is correct
34 Correct 2 ms 8540 KB Output is correct
35 Correct 1 ms 8540 KB Output is correct
36 Correct 2 ms 8540 KB Output is correct
37 Correct 1 ms 8540 KB Output is correct
38 Correct 2 ms 8540 KB Output is correct
39 Correct 1 ms 8540 KB Output is correct
40 Correct 2 ms 8540 KB Output is correct
41 Correct 166 ms 19156 KB Output is correct
42 Correct 298 ms 28876 KB Output is correct
43 Correct 325 ms 29132 KB Output is correct
44 Correct 73 ms 15356 KB Output is correct
45 Correct 322 ms 37208 KB Output is correct
46 Correct 312 ms 37072 KB Output is correct
47 Correct 292 ms 37060 KB Output is correct
48 Correct 303 ms 37188 KB Output is correct
49 Correct 315 ms 37000 KB Output is correct
50 Correct 315 ms 37184 KB Output is correct
51 Correct 292 ms 37328 KB Output is correct
52 Correct 349 ms 37176 KB Output is correct
53 Correct 305 ms 37080 KB Output is correct
54 Correct 326 ms 37072 KB Output is correct
55 Correct 299 ms 37584 KB Output is correct
56 Correct 296 ms 37064 KB Output is correct
57 Correct 309 ms 37068 KB Output is correct
58 Correct 337 ms 37352 KB Output is correct
59 Correct 57 ms 16724 KB Output is correct
60 Correct 308 ms 37008 KB Output is correct
61 Correct 301 ms 37232 KB Output is correct
62 Correct 64 ms 18280 KB Output is correct
63 Correct 80 ms 17220 KB Output is correct
64 Correct 82 ms 18248 KB Output is correct
65 Correct 63 ms 18240 KB Output is correct
66 Correct 81 ms 17488 KB Output is correct
67 Correct 66 ms 16836 KB Output is correct
68 Correct 64 ms 18248 KB Output is correct
69 Correct 62 ms 16724 KB Output is correct
70 Correct 65 ms 18504 KB Output is correct
71 Correct 63 ms 16596 KB Output is correct
72 Correct 209 ms 33128 KB Output is correct
73 Correct 358 ms 48336 KB Output is correct
74 Correct 365 ms 48332 KB Output is correct
75 Correct 364 ms 48212 KB Output is correct
76 Correct 347 ms 48336 KB Output is correct
77 Correct 366 ms 48628 KB Output is correct
78 Correct 343 ms 48252 KB Output is correct
79 Correct 376 ms 48352 KB Output is correct
80 Correct 352 ms 48328 KB Output is correct
81 Correct 358 ms 48288 KB Output is correct
82 Correct 376 ms 48468 KB Output is correct
83 Correct 359 ms 48348 KB Output is correct
84 Correct 395 ms 48556 KB Output is correct
85 Correct 349 ms 47896 KB Output is correct
86 Correct 351 ms 48456 KB Output is correct
87 Correct 390 ms 48224 KB Output is correct
88 Correct 408 ms 48572 KB Output is correct
89 Correct 137 ms 29640 KB Output is correct
90 Correct 359 ms 48332 KB Output is correct
91 Correct 355 ms 46860 KB Output is correct
92 Correct 94 ms 27468 KB Output is correct
93 Correct 150 ms 28396 KB Output is correct
94 Correct 104 ms 27464 KB Output is correct
95 Correct 95 ms 27208 KB Output is correct
96 Correct 137 ms 26504 KB Output is correct
97 Correct 146 ms 28116 KB Output is correct
98 Correct 94 ms 26948 KB Output is correct
99 Correct 120 ms 28080 KB Output is correct
100 Correct 95 ms 27532 KB Output is correct