oj.uz

Submission #708061

# Submission time Handle Problem Language Result Execution time Memory
708061 2023-03-11T02:50:46 Z Github Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 507 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, 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 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 1 ms 340 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 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 4 ms 852 KB Output is correct
13 Correct 4 ms 980 KB Output is correct
14 Correct 1 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 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 4 ms 852 KB Output is correct
13 Correct 4 ms 980 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 387 ms 65384 KB Output is correct
17 Correct 69 ms 14344 KB Output is correct
18 Correct 90 ms 16544 KB Output is correct
19 Correct 507 ms 72908 KB Output is correct
20 Correct 286 ms 52692 KB Output is correct
21 Correct 31 ms 6576 KB Output is correct
22 Correct 283 ms 48196 KB Output is correct