oj.uz

Submission #971517

# Submission time Handle Problem Language Result Execution time Memory
971517 2024-04-28T17:45:14 Z Spade1 Evacuation plan (IZhO18_plan) C++14
19 / 100
 272 ms 29808 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;
  int cnt = 0;
  while (u != v) {
    ckmin(ret, par[u].nd), u = par[u].st;
    ckmin(ret, par[v].nd), v = par[v].st;
  }
  return min(ret, par[u].nd);
}

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 'int query(int, int)':
plan.cpp:66:7: warning: unused variable 'cnt' [-Wunused-variable]
   66 |   int cnt = 0;
      |       ^~~
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 4440 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Incorrect 1 ms 4444 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Incorrect 1 ms 4444 KB Output isn't correct
8 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 133 ms 12628 KB Output is correct
2 Correct 259 ms 21076 KB Output is correct
3 Correct 226 ms 21112 KB Output is correct
4 Correct 45 ms 8916 KB Output is correct
5 Correct 239 ms 29404 KB Output is correct
6 Correct 223 ms 29388 KB Output is correct
7 Correct 254 ms 29384 KB Output is correct
8 Correct 234 ms 29448 KB Output is correct
9 Correct 241 ms 29396 KB Output is correct
10 Correct 233 ms 29328 KB Output is correct
11 Correct 233 ms 29380 KB Output is correct
12 Correct 239 ms 29232 KB Output is correct
13 Correct 272 ms 29444 KB Output is correct
14 Correct 242 ms 29388 KB Output is correct
15 Correct 261 ms 29808 KB Output is correct
16 Correct 217 ms 29312 KB Output is correct
17 Correct 216 ms 29384 KB Output is correct
18 Correct 229 ms 29284 KB Output is correct
19 Correct 38 ms 10708 KB Output is correct
20 Correct 219 ms 29432 KB Output is correct
21 Correct 214 ms 29568 KB Output is correct
22 Correct 48 ms 12424 KB Output is correct
23 Correct 61 ms 10988 KB Output is correct
24 Correct 54 ms 12620 KB Output is correct
25 Correct 49 ms 12616 KB Output is correct
26 Correct 63 ms 11208 KB Output is correct
27 Correct 38 ms 10444 KB Output is correct
28 Correct 61 ms 12516 KB Output is correct
29 Correct 40 ms 10656 KB Output is correct
30 Correct 50 ms 12620 KB Output is correct
31 Correct 37 ms 10484 KB Output is correct

Subtask #5
0 / 46.0

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