oj.uz

Submission #1011346

# Submission time Handle Problem Language Result Execution time Memory
1011346 2024-06-30T11:34:30 Z Braabebo10 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 287 ms 91336 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 0 ms 4440 KB Output is correct
2 Correct 1 ms 4440 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 4444 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4440 KB Output is correct
2 Correct 1 ms 4440 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 4444 KB Output is correct
9 Correct 2 ms 4812 KB Output is correct
10 Correct 1 ms 4448 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 2 ms 4960 KB Output is correct
13 Correct 2 ms 5060 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 0 ms 4440 KB Output is correct
2 Correct 1 ms 4440 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 4444 KB Output is correct
9 Correct 2 ms 4812 KB Output is correct
10 Correct 1 ms 4448 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 2 ms 4960 KB Output is correct
13 Correct 2 ms 5060 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 249 ms 82180 KB Output is correct
17 Correct 48 ms 19284 KB Output is correct
18 Correct 56 ms 21840 KB Output is correct
19 Correct 287 ms 91336 KB Output is correct
20 Correct 172 ms 66392 KB Output is correct
21 Correct 22 ms 11096 KB Output is correct
22 Correct 194 ms 64284 KB Output is correct