oj.uz

Submission #971520

# Submission time Handle Problem Language Result Execution time Memory
971520 2024-04-28T17:53:29 Z Spade1 Evacuation plan (IZhO18_plan) C++14
19 / 100
 265 ms 21616 KB 
#pragma once
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pld> vpld;
typedef vector<vi> vvi;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;

template<typename T> using pq = priority_queue<T>;
template<typename T> using pqg = priority_queue<T, vector<T>, greater<T>>;

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin(), (x).end()
#define ins insert

template<typename T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1e9 + 7;
const int INF = 0x3fffffff;
const ll LINF = 0x1fffffffffffffff;
const char nl = '\n';
const int MX = 1e5 + 3;

vpii adj[MX];
int dis[MX], rnk[MX], lvl[MX];
pii par[MX];

int f(int i) {
  if (par[i].st == i) return i;
  lvl[i] = lvl[par[i].st]+1;
  return f(par[i].st);
} 

void join(int a, int b, int w) {
  int fa = f(a), fb = f(b);
  if (rnk[fa] > rnk[fb]) swap(fa, fb);
  par[fa] = {fb, w};
  rnk[fb] += (rnk[fb] == rnk[fa]);
}

int query(int u, int v) {
  int ret = INF;
  if (lvl[u] < lvl[v]) swap(u, v);
  while (lvl[v] < lvl[u]) ckmin(ret, par[u].nd), u = par[u].st;
  if (u == v) return min(ret, par[u].nd);
  while (u != v) {
    ckmin(ret, par[u].nd), u = par[u].st;
    ckmin(ret, par[v].nd), v = par[v].st;
  }
  return ret;
}

void solve() {
  int n, m; cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int u, v, w; cin >> u >> v >> w;
    adj[u].pb({v, w}); adj[v].pb({u, w});
  }
  pqg<pii> pq;
  fill(dis, dis+MX, INF);
  int k; cin >> k;
  for (int i = 1; i <= k; ++i) {
    int g; cin >> g; 
    pq.push({dis[g] = 0, g});
  }
  //dijkstra
  while (!pq.empty()) {
    auto [cur, a] = pq.top(); pq.pop();
    if (cur > dis[a]) continue;
    for (auto [b, w] : adj[a]) {
      if (ckmin(dis[b], dis[a]+w)) pq.push({dis[b], b});
    }
  }

  vpii v;
  for (int i = 1; i <= n; ++i) v.pb({-dis[i], i}), par[i] = {i, dis[i]};
  //DSU by rank
  sort(all(v));
  for (auto [w, a] : v) {
    for (auto [b, w] : adj[a]) {
      if (dis[b] >= dis[a] && f(a) != f(b)) join(a, b, dis[a]); 
    }
  }
  //finding the levels
  for (int i = 1; i <= n; ++i) f(i);

  int q; cin >> q;
  while (q--) {
    int u, v; cin >> u >> v;
    cout << query(u, v) << nl;
  }
}

int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0); cin.tie(NULL);
  int t = 1;
  // cin >> t;
  while (t--) { solve(); }
  return 0;
}

Compilation message

plan.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
plan.cpp: In function 'void solve()':
plan.cpp:89:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |     auto [cur, a] = pq.top(); pq.pop();
      |          ^
plan.cpp:91:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   91 |     for (auto [b, w] : adj[a]) {
      |               ^
plan.cpp:100:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  100 |   for (auto [w, a] : v) {
      |             ^
plan.cpp:101:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  101 |     for (auto [b, w] : adj[a]) {
      |               ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Incorrect 2 ms 4440 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Incorrect 2 ms 4440 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 12628 KB Output is correct
2 Correct 265 ms 21172 KB Output is correct
3 Correct 227 ms 21240 KB Output is correct
4 Correct 39 ms 8904 KB Output is correct
5 Correct 221 ms 21224 KB Output is correct
6 Correct 255 ms 21284 KB Output is correct
7 Correct 215 ms 21316 KB Output is correct
8 Correct 235 ms 21388 KB Output is correct
9 Correct 201 ms 21196 KB Output is correct
10 Correct 228 ms 21292 KB Output is correct
11 Correct 236 ms 21148 KB Output is correct
12 Correct 202 ms 21192 KB Output is correct
13 Correct 208 ms 21292 KB Output is correct
14 Correct 227 ms 21196 KB Output is correct
15 Correct 200 ms 21616 KB Output is correct
16 Correct 216 ms 21284 KB Output is correct
17 Correct 205 ms 21172 KB Output is correct
18 Correct 217 ms 21192 KB Output is correct
19 Correct 37 ms 8916 KB Output is correct
20 Correct 235 ms 21304 KB Output is correct
21 Correct 193 ms 20940 KB Output is correct
22 Correct 49 ms 10816 KB Output is correct
23 Correct 49 ms 9428 KB Output is correct
24 Correct 52 ms 10980 KB Output is correct
25 Correct 47 ms 10824 KB Output is correct
26 Correct 51 ms 9424 KB Output is correct
27 Correct 38 ms 8916 KB Output is correct
28 Correct 48 ms 10836 KB Output is correct
29 Correct 38 ms 8908 KB Output is correct
30 Correct 47 ms 10908 KB Output is correct
31 Correct 47 ms 8912 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Incorrect 2 ms 4440 KB Output isn't correct
10 Halted 0 ms 0 KB -