oj.uz

Submission #1099134

# Submission time Handle Problem Language Result Execution time Memory
1099134 2024-10-10T15:32:56 Z akamizane Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 368 ms 90244 KB 
#include<bits/stdc++.h>
 
using namespace std;

using ll = long long;
using pii = pair<int,long long>;
 
#define el cout << '\n'
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T1, class T2>bool chmax(T1 &a, T2 b){if (a < b) {a = b; return true;}return false;}
template <class T1, class T2>bool chmin(T1 &a, T2 b){if (a > b) {a = b; return true;}return false;}
 
ll travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
  int n, m, k;
  n = N, m = M, k = K;
  vector<vector<pair<int,long long>>> ad(n);
  REP(i, m){
    int u, v, w;
    u = R[i][0], v = R[i][1], w = L[i];
    ad[u].pb({v, w});
    ad[v].pb({u, w});
  }
  vector<vector<ll>> d(n, vector<ll> (2, 1e18));
  using T = pair<long long, int>;
  priority_queue<T, vector<T>, greater<T>> pq;
  REP(i, k){
    int p;
    p = P[i];
    d[p][0] = d[p][1] = 0;
    pq.push({0, p});
  }
  while(pq.size()){
    auto [val, u] = pq.top();
    pq.pop();
    if (val != d[u][1]) continue;
    for (auto [v, w] : ad[u]){
      if (val + w < d[v][0]){
        if (d[v][0] != d[v][1] && d[v][0] < 1e18){
          d[v][1] = d[v][0];
          pq.push({d[v][1], v});
        }
        d[v][0] = val + w;
      }
      else if (val + w < d[v][1]){
        d[v][1] = val + w;
        pq.push({d[v][1], v});
      }
    }
  }
  return d[0][1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 2 ms 1116 KB Output is correct
13 Correct 2 ms 1116 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 2 ms 1116 KB Output is correct
13 Correct 2 ms 1116 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 327 ms 81872 KB Output is correct
17 Correct 56 ms 21588 KB Output is correct
18 Correct 85 ms 23180 KB Output is correct
19 Correct 368 ms 90244 KB Output is correct
20 Correct 186 ms 65620 KB Output is correct
21 Correct 27 ms 9308 KB Output is correct
22 Correct 204 ms 63724 KB Output is correct