oj.uz

Submission #1041431

# Submission time Handle Problem Language Result Execution time Memory
1041431 2024-08-02T03:47:08 Z HappyCapybara Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 446 ms 64956 KB 
#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
  vector<vector<pair<int,int>>> g(N);
  for (int i=0; i<M; i++){
    g[R[i][0]].push_back({R[i][1], L[i]});
    g[R[i][1]].push_back({R[i][0], L[i]});
  }
  vector<pair<int,int>> v(N, {pow(10, 9)+1, pow(10, 9)+1});
  priority_queue<pair<int,int>> pq;
  for (int i=0; i<K; i++) pq.push({0, P[i]});
  vector<bool> seen(N, false);
  while (!pq.empty()){
    int d = -pq.top().first, cur = pq.top().second;
    pq.pop();
    if (seen[cur]) continue;
    seen[cur] = true;
    //cout << cur << " " << d << "\n";
    for (pair<int,int> next : g[cur]){
      if (d + next.second < v[next.first].first){
        v[next.first].second = v[next.first].first;
        v[next.first].first = d + next.second;
      }
      else if (d + next.second < v[next.first].second) v[next.first].second = d + next.second;
      if (v[next.first].second < pow(10, 9)+1) pq.push({-v[next.first].second, next.first});
    }
  }
  return v[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 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 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 4440 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 1 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 4440 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 4 ms 4916 KB Output is correct
13 Correct 4 ms 4956 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 1 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 4440 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 1 ms 4700 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 4 ms 4916 KB Output is correct
13 Correct 4 ms 4956 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 433 ms 64956 KB Output is correct
17 Correct 45 ms 15396 KB Output is correct
18 Correct 57 ms 16988 KB Output is correct
19 Correct 446 ms 64532 KB Output is correct
20 Correct 297 ms 52620 KB Output is correct
21 Correct 21 ms 9164 KB Output is correct
22 Correct 276 ms 46124 KB Output is correct