oj.uz

Submission #996193

# Submission time Handle Problem Language Result Execution time Memory
996193 2024-06-10T08:38:28 Z 54skyxenon Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 1786 ms 140084 KB 
// https://oj.uz/problem/view/IOI11_crocodile

/** Needed for linking!!! */
#include "crocodile.h"

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define INF (ll)1e18

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    vector<map<int, int>> graph(N);
    vector<set<int>> visited(N);

    for (int i = 0; i < M; i++) {
        int u = R[i][0];
        int v = R[i][1];
        graph[u][v] = graph[v][u] = L[i];
    }

    // Run Dijkstra's and only care about the second best distance, propagated downwards
    vector<vector<ll>> dist(graph.size(), {INF, INF});
    priority_queue<pair<ll, ll>> pq;

    for (int i = 0; i < K; i++) {
        pq.push({0, P[i]});
        dist[P[i]][0] = dist[P[i]][1] = 0;
    }

    while (pq.size()) {
        auto [d, u] = pq.top();
        pq.pop();
        d = -d;

        if (d > dist[u][1]) {
            continue;
        }

        // Thank you to Sreepranad Devarakonda from USACO Guide
        for (auto& [v, w] : graph[u]) {
            ll cost = w + d;

            // ! We only add to the priority queue (for a downstream effect) when we set the 2nd shortest distance
            if (cost < dist[v][0]) {
                // The first shortest distance can become the 2nd shortest distance
                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] = cost;
            }
            else if (cost < dist[v][1]) {
                dist[v][1] = cost;
                pq.push({-cost, v});
            }
        }
    }

    return dist[0][1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 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 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4724 KB Output is correct
7 Correct 2 ms 4800 KB Output is correct
8 Correct 1 ms 4696 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 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 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4724 KB Output is correct
7 Correct 2 ms 4800 KB Output is correct
8 Correct 1 ms 4696 KB Output is correct
9 Correct 4 ms 4952 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 3 ms 4748 KB Output is correct
12 Correct 8 ms 5464 KB Output is correct
13 Correct 4 ms 5468 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4700 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 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 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4724 KB Output is correct
7 Correct 2 ms 4800 KB Output is correct
8 Correct 1 ms 4696 KB Output is correct
9 Correct 4 ms 4952 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 3 ms 4748 KB Output is correct
12 Correct 8 ms 5464 KB Output is correct
13 Correct 4 ms 5468 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4700 KB Output is correct
16 Correct 1786 ms 114736 KB Output is correct
17 Correct 68 ms 40848 KB Output is correct
18 Correct 89 ms 42100 KB Output is correct
19 Correct 1704 ms 140084 KB Output is correct
20 Correct 637 ms 116696 KB Output is correct
21 Correct 37 ms 18840 KB Output is correct
22 Correct 493 ms 112380 KB Output is correct