oj.uz

Submission #953558

# Submission time Handle Problem Language Result Execution time Memory
953558 2024-03-26T07:49:59 Z Trisanu_Das Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 398 ms 90272 KB 
#include <bits/stdc++.h>
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 2 ms 4440 KB Output is correct
2 Correct 1 ms 4444 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 2 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 2 ms 4440 KB Output is correct
2 Correct 1 ms 4444 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 2 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 5164 KB Output is correct
13 Correct 3 ms 5212 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 2 ms 4444 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4440 KB Output is correct
2 Correct 1 ms 4444 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 2 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 5164 KB Output is correct
13 Correct 3 ms 5212 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 2 ms 4444 KB Output is correct
16 Correct 319 ms 82076 KB Output is correct
17 Correct 58 ms 19288 KB Output is correct
18 Correct 73 ms 21844 KB Output is correct
19 Correct 398 ms 90272 KB Output is correct
20 Correct 221 ms 66384 KB Output is correct
21 Correct 28 ms 11040 KB Output is correct
22 Correct 245 ms 64188 KB Output is correct