oj.uz

답안 #971515

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
971515 2024-04-28T17:39:16 Z Spade1 Evacuation plan (IZhO18_plan) C++14
0 / 100
 4000 ms 29388 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;
  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 'void solve()':
plan.cpp:88:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |     auto [cur, a] = pq.top(); pq.pop();
      |          ^
plan.cpp:90:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   90 |     for (auto [b, w] : adj[a]) {
      |               ^
plan.cpp:99:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |   for (auto [w, a] : v) {
      |             ^
plan.cpp:100:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  100 |     for (auto [b, w] : adj[a]) {
      |               ^

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4612 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 1 ms 4544 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Execution timed out 4088 ms 4444 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4612 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 1 ms 4544 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Execution timed out 4088 ms 4444 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 16032 KB Output is correct
2 Correct 272 ms 29388 KB Output is correct
3 Correct 248 ms 29384 KB Output is correct
4 Execution timed out 4046 ms 10604 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4612 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 1 ms 4544 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Execution timed out 4088 ms 4444 KB Time limit exceeded
7 Halted 0 ms 0 KB -