oj.uz

Submission #1088003

# Submission time Handle Problem Language Result Execution time Memory
1088003 2024-09-13T16:47:43 Z T0p_ Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 815 ms 117556 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000 + 5;

struct Dijkstra {
  int node;
  long long weight;

  bool operator < (const Dijkstra & o) const {
    return weight > o.weight;
  }
};

int visited[MAX_N];
long long dis[MAX_N];
vector<pair<int, long long>> g[MAX_N];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
  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] });
  }

  for (int i=0 ; i<N ; i++) {
    dis[i] = 2e9;
  }

  priority_queue<Dijkstra> dijkstra;

  for (int i=0 ; i<K ; i++) {
    dis[P[i]] = 0;
    visited[P[i]] = 1;
    dijkstra.push({ P[i], 0 });
  }

  while (!dijkstra.empty()) {
    int node = dijkstra.top().node;
    long long weight = dijkstra.top().weight;
    dijkstra.pop();

    if (visited[node] == 2) continue;
    visited[node]++;

    if (visited[node] == 2) {
      dis[node] = weight;
      for (pair<int, long long> edge : g[node]) {
        dijkstra.push({ edge.first, weight + edge.second });
      }
    }
  }
  return dis[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2648 KB Output is correct
4 Correct 3 ms 2808 KB Output is correct
5 Correct 2 ms 2924 KB Output is correct
6 Correct 2 ms 2804 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2648 KB Output is correct
4 Correct 3 ms 2808 KB Output is correct
5 Correct 2 ms 2924 KB Output is correct
6 Correct 2 ms 2804 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 4 ms 3420 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 3 ms 3068 KB Output is correct
12 Correct 5 ms 4080 KB Output is correct
13 Correct 5 ms 4068 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 3 ms 2908 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2648 KB Output is correct
4 Correct 3 ms 2808 KB Output is correct
5 Correct 2 ms 2924 KB Output is correct
6 Correct 2 ms 2804 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 4 ms 3420 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 3 ms 3068 KB Output is correct
12 Correct 5 ms 4080 KB Output is correct
13 Correct 5 ms 4068 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 3 ms 2908 KB Output is correct
16 Correct 815 ms 113560 KB Output is correct
17 Correct 65 ms 17236 KB Output is correct
18 Correct 86 ms 19676 KB Output is correct
19 Correct 751 ms 117556 KB Output is correct
20 Correct 498 ms 101164 KB Output is correct
21 Correct 28 ms 9564 KB Output is correct
22 Correct 392 ms 64908 KB Output is correct