oj.uz

Submission #943967

# Submission time Handle Problem Language Result Execution time Memory
943967 2024-03-12T05:46:43 Z Amaarsaa Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 397 ms 91844 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define ll long long
#define INF 1e18

ll travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    int n = N, m = M, k = K;
    vector<vector<pair<int, ll>>> graph(n);
    for (int i = 0; i < m; i++){
        graph[R[i][0]].push_back({R[i][1], L[i]});
        graph[R[i][1]].push_back({R[i][0], L[i]});
    }
    ll dist[n][2];
    for (int i = 0; i < n; i++){
        dist[i][0] = INF, dist[i][1] = INF;
    }
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    for (int i = 0; i < k; i++){
        dist[P[i]][0] = 0;
        dist[P[i]][1] = 0;
        pq.push({0, P[i]});
    }
    while (!pq.empty()){
        ll cur_dis = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if (cur_dis != dist[u][1]){
            continue;
        }
        for (pair<int, int> p: graph[u]){
            int v = p.first, w = p.second;
            if (dist[v][0] > w + cur_dis){
                if (dist[v][0] != dist[v][1] && dist[v][0] < INF){
                    dist[v][1] = dist[v][0];
                    pq.push({dist[v][1], v});
                }
                dist[v][0] = w+cur_dis;
            }else if (dist[v][1] > w + cur_dis){
                dist[v][1] = w + cur_dis;
                pq.push({dist[v][1], v});
            }
        }
    }
    return dist[0][1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 4492 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 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 2 ms 4492 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 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 4700 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 2 ms 4700 KB Output is correct
12 Correct 3 ms 4956 KB Output is correct
13 Correct 3 ms 5088 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 2 ms 4492 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 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 4700 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 2 ms 4700 KB Output is correct
12 Correct 3 ms 4956 KB Output is correct
13 Correct 3 ms 5088 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 316 ms 82080 KB Output is correct
17 Correct 55 ms 19280 KB Output is correct
18 Correct 69 ms 21660 KB Output is correct
19 Correct 397 ms 91844 KB Output is correct
20 Correct 223 ms 66384 KB Output is correct
21 Correct 27 ms 11124 KB Output is correct
22 Correct 267 ms 64304 KB Output is correct