oj.uz

Submission #284500

# Submission time Handle Problem Language Result Execution time Memory
284500 2020-08-27T14:04:42 Z IOrtroiii Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 738 ms 70900 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>>> adj(N);
   for (int i = 0; i < M; ++i) {
      adj[R[i][0]].emplace_back(R[i][1], L[i]);
      adj[R[i][1]].emplace_back(R[i][0], L[i]);
   }
   vector<int> cnts(N);
   priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
   for (int i = 0; i < K; ++i) {
      q.emplace(0, P[i]);
      q.emplace(0, P[i]);
   }
   while (!q.empty()) {
      int d, v; tie(d, v) = q.top(); q.pop();
      if (++cnts[v] == 2) {
         if (v == 0) return d;
         for (auto e : adj[v]) {
            q.emplace(d + e.second, e.first);
         }
      }
   }
   assert(false);
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 384 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 2 ms 556 KB Output is correct
12 Correct 7 ms 1152 KB Output is correct
13 Correct 4 ms 896 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 2 ms 556 KB Output is correct
12 Correct 7 ms 1152 KB Output is correct
13 Correct 4 ms 896 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 686 ms 70900 KB Output is correct
17 Correct 115 ms 13304 KB Output is correct
18 Correct 131 ms 14960 KB Output is correct
19 Correct 738 ms 67032 KB Output is correct
20 Correct 399 ms 47204 KB Output is correct
21 Correct 56 ms 5880 KB Output is correct
22 Correct 687 ms 44848 KB Output is correct