oj.uz

Submission #708060

# Submission time Handle Problem Language Result Execution time Memory
708060 2023-03-11T02:49:12 Z Github Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 470 ms 72908 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;

#define speedup ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#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, pair<int, int>>, vector<pair<ll, pair<int, int>>>, greater<pair<ll, pair<int, int>>>> pq;
    for (int i = 0; i < k; i++){
        dist[P[i]][0] = 0;
        dist[P[i]][1] = 0;
        pq.push({0, {P[i], 1}});
    }
    while (!pq.empty()){
        ll cur_dis = pq.top().first;
        int u = pq.top().second.first, type = pq.top().second.second;
        pq.pop();
        if (cur_dis != dist[u][type]){
            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, 1}});
                }
                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, 1}});
            }
        }
    }
    return dist[0][1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 356 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 356 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 424 KB Output is correct
12 Correct 3 ms 920 KB Output is correct
13 Correct 3 ms 980 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 356 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 424 KB Output is correct
12 Correct 3 ms 920 KB Output is correct
13 Correct 3 ms 980 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 364 ms 65340 KB Output is correct
17 Correct 61 ms 14368 KB Output is correct
18 Correct 81 ms 16628 KB Output is correct
19 Correct 470 ms 72908 KB Output is correct
20 Correct 243 ms 52812 KB Output is correct
21 Correct 30 ms 6652 KB Output is correct
22 Correct 251 ms 48200 KB Output is correct