oj.uz

Submission #955946

# Submission time Handle Problem Language Result Execution time Memory
955946 2024-03-31T17:53:32 Z Maaxle Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 614 ms 104480 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define uset unordered_set
#define umap unordered_map 
#define pqueue priority_queue

using namespace std;

struct res {
    ll i, sum;  
};
bool operator < (const res& i, const res& j) { return (i.sum > j.sum); }

vector<vector<pair<ll, ll>>> adj;
vector<pair<ll, ll>> memo;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
  adj.resize(N);
  memo.resize(N, {((ll) 1 << 60), ((ll) 1 << 60)});
  
  range(i, 0, M) {
      adj[R[i][0]].push_back({R[i][1], L[i]});
      adj[R[i][1]].push_back({R[i][0], L[i]});
  }

  pqueue<res> pq;
  range(i, 0, K) {
      memo[P[i]].first = 0;
      pq.push({P[i], 0});
  }

  res t;
  vector<int> visited (N);
  while (!pq.empty()) {
      t = pq.top(); pq.pop();
      ll sec = memo[t.i].second;
      visited[t.i]++;

      if (t.sum <= memo[t.i].first) {
          memo[t.i].second = memo[t.i].first;
          memo[t.i].first = t.sum;
      }
      else memo[t.i].second = min(memo[t.i].second, t.sum);

      if (sec != memo[t.i].second) {
          for (pair<ll, ll> k : adj[t.i]) {
              if (visited[k.first] < 2) {
                  pq.push({k.first, memo[t.i].second + k.second});
              }
          }
      }
    }
    return memo[0].second;
}

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 4700 KB Output is correct
4 Correct 1 ms 4552 KB Output is correct
5 Correct 3 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 1 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 4700 KB Output is correct
4 Correct 1 ms 4552 KB Output is correct
5 Correct 3 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 1 ms 4444 KB Output is correct
9 Correct 3 ms 4956 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 2 ms 4700 KB Output is correct
12 Correct 4 ms 5468 KB Output is correct
13 Correct 4 ms 5468 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 4700 KB Output is correct
4 Correct 1 ms 4552 KB Output is correct
5 Correct 3 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 1 ms 4444 KB Output is correct
9 Correct 3 ms 4956 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 2 ms 4700 KB Output is correct
12 Correct 4 ms 5468 KB Output is correct
13 Correct 4 ms 5468 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 484 ms 97924 KB Output is correct
17 Correct 59 ms 19796 KB Output is correct
18 Correct 76 ms 22020 KB Output is correct
19 Correct 614 ms 104480 KB Output is correct
20 Correct 365 ms 83968 KB Output is correct
21 Correct 37 ms 11288 KB Output is correct
22 Correct 306 ms 64792 KB Output is correct