| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 944000 | 2024-03-12T06:28:01 Z | Amaarsaa | Crocodile's Underground City (IOI11_crocodile) | C++14 | 420 ms | 83240 KB |
#include<bits/stdc++.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
using ll = long long;
using pll = pair < ll, ll >;
const ll INF = 1e18;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
ll i, x, c, y, s, p, X;
vector < pair < ll,ll > > adj[N + 2];
for (i = 0; i < M; i ++) {
x = R[i][0];
y = R[i][1];
adj[x].push_back({y, L[i]});
adj[y].push_back({x, L[i]});
}
priority_queue < pll, vector < pll > , greater < pll > > pq;
ll D[N + 2][3];
for (i = 0; i < N; i ++) D[i][1] = INF, D[i][0] = INF;
for (i = 0; i < K; i ++) {
pq.push({0, P[i]});
D[P[i]][0] = D[P[i]][1] = 0;
}
while(!pq.empty()) {
x = pq.top().second;
c = pq.top().first;
pq.pop();
if ( D[x][1] != c) continue;
for ( pair < ll, ll > pa : adj[x]) {
X = pa.first;
s = pa.second;
p = D[X][1];
if ( s + c < D[X][0]) {
if ( D[X][0] < INF && D[X][1] != D[X][0]) {
D[X][1]= D[X][0];
pq.push({D[X][1], X});
}
D[X][0] = s + c;
}
else {
if ( s + c< D[X][1]) {
D[X][1] = s + c;
pq.push({D[X][1], X});
}
}
}
}
return D[0][1];
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 4440 KB | Output is correct |
| 2 | Correct | 2 ms | 4444 KB | Output is correct |
| 3 | Correct | 3 ms | 4444 KB | Output is correct |
| 4 | Correct | 1 ms | 4440 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 |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 4440 KB | Output is correct |
| 2 | Correct | 2 ms | 4444 KB | Output is correct |
| 3 | Correct | 3 ms | 4444 KB | Output is correct |
| 4 | Correct | 1 ms | 4440 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 | 3 ms | 4700 KB | Output is correct |
| 10 | Correct | 1 ms | 4444 KB | Output is correct |
| 11 | Correct | 1 ms | 4576 KB | Output is correct |
| 12 | Correct | 3 ms | 4956 KB | Output is correct |
| 13 | Correct | 3 ms | 5212 KB | Output is correct |
| 14 | Correct | 1 ms | 4444 KB | Output is correct |
| 15 | Correct | 1 ms | 4444 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 4440 KB | Output is correct |
| 2 | Correct | 2 ms | 4444 KB | Output is correct |
| 3 | Correct | 3 ms | 4444 KB | Output is correct |
| 4 | Correct | 1 ms | 4440 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 | 3 ms | 4700 KB | Output is correct |
| 10 | Correct | 1 ms | 4444 KB | Output is correct |
| 11 | Correct | 1 ms | 4576 KB | Output is correct |
| 12 | Correct | 3 ms | 4956 KB | Output is correct |
| 13 | Correct | 3 ms | 5212 KB | Output is correct |
| 14 | Correct | 1 ms | 4444 KB | Output is correct |
| 15 | Correct | 1 ms | 4444 KB | Output is correct |
| 16 | Correct | 317 ms | 74448 KB | Output is correct |
| 17 | Correct | 56 ms | 18768 KB | Output is correct |
| 18 | Correct | 74 ms | 21072 KB | Output is correct |
| 19 | Correct | 420 ms | 83240 KB | Output is correct |
| 20 | Correct | 229 ms | 59956 KB | Output is correct |
| 21 | Correct | 28 ms | 11088 KB | Output is correct |
| 22 | Correct | 289 ms | 57708 KB | Output is correct |