oj.uz

Submission #955367

# Submission time Handle Problem Language Result Execution time Memory
955367 2024-03-30T09:03:19 Z blackslex Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 444 ms 91068 KB 
#include "crocodile.h"
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;

ll n, m, k;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  n = N; m = M; k = K;
  vector<vector<pii>> v(n, vector<pii>());
  for (int i = 0; i < m; i++) v[R[i][0]].emplace_back(R[i][1], L[i]), v[R[i][1]].emplace_back(R[i][0], L[i]);
  for (int i = 0; i < n; i++) sort(v[i].begin(), v[i].end(), [&] (const pii &p1, const pii &p2) {
    return p1.second < p2.second;
  });
  priority_queue<pii, vector<pii>, greater<pii>> pq;
  vector<pii> d(n, pii(1e18, 1e18));
  vector<bool> f(n);
  for (int i = 0; i < k; i++) d[P[i]] = pii(0, 0), pq.emplace(0, P[i]);
  while (!pq.empty()) {
    auto [nd, nn] = pq.top(); pq.pop();
    if (f[nn]) continue; f[nn] = 1;
    for (auto &[tn, td]: v[nn]) {
      if (d[tn].second > d[nn].second + td) {
        d[tn].second = d[nn].second + td;
        if (d[tn].second < d[tn].first) swap(d[tn].second, d[tn].first);
        if (d[tn].second != 1e18) pq.emplace(d[tn].second, tn);
      }
    }
  }
  return d[0].second;
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:23:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   23 |     if (f[nn]) continue; f[nn] = 1;
      |     ^~
crocodile.cpp:23:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   23 |     if (f[nn]) continue; f[nn] = 1;
      |                          ^

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 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 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 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 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4696 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 4 ms 5316 KB Output is correct
13 Correct 4 ms 5236 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 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 Correct 1 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4696 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 4 ms 5316 KB Output is correct
13 Correct 4 ms 5236 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 372 ms 82204 KB Output is correct
17 Correct 58 ms 19536 KB Output is correct
18 Correct 75 ms 21760 KB Output is correct
19 Correct 444 ms 91068 KB Output is correct
20 Correct 252 ms 66340 KB Output is correct
21 Correct 29 ms 11100 KB Output is correct
22 Correct 284 ms 64420 KB Output is correct