oj.uz

Submission #1039906

# Submission time Handle Problem Language Result Execution time Memory
1039906 2024-07-31T11:58:37 Z vjudge1 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 1357 ms 211212 KB 
#include "bits/stdc++.h"
#include "crocodile.h"
#define i64 long long

using namespace std;

const i64 inf = 1e18 + 18;
const i64 sz = 1e5 + 5;

vector<vector<i64>> aj[sz];

bool vi[sz];
i64 d[sz][2];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    for (int i = 0; i < M; i++) {
        i64 le = R[i][0];
        i64 ri = R[i][1];
        aj[le].push_back({ri, L[i]});
        aj[ri].push_back({le, L[i]});
    }

    for (i64 i = 0; i < N; i++) {
        d[i][0] = inf;
        d[i][1] = inf;
    }

    priority_queue<vector<i64>> pq;

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

    while (!pq.empty()) {
        auto vc = pq.top();
        pq.pop();
        i64 v = vc[1];
        i64 ev = -vc[0];

        if (vi[v]) {
            continue;
        }

        vi[v] = true;

        if (ev >= inf) {
            continue;
        }

        for (auto& uc : aj[v]) {
            i64 u = uc[0];
            i64 eu = uc[1];

            if (vi[u]) {
                continue;
            }

            if (ev + eu < d[u][0]) {
                d[u][1] = d[u][0];
                d[u][0] = ev + eu;
            } else {
                d[u][1] = min(d[u][1], ev + eu);
            }

            pq.push({-d[u][1], u});
        }
    }

    return d[0][1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6548 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6548 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 4 ms 7512 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 2 ms 6880 KB Output is correct
12 Correct 6 ms 8284 KB Output is correct
13 Correct 6 ms 8540 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6548 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 4 ms 7512 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 2 ms 6880 KB Output is correct
12 Correct 6 ms 8284 KB Output is correct
13 Correct 6 ms 8540 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct
16 Correct 1226 ms 204476 KB Output is correct
17 Correct 89 ms 41992 KB Output is correct
18 Correct 130 ms 43708 KB Output is correct
19 Correct 1357 ms 211212 KB Output is correct
20 Correct 693 ms 174312 KB Output is correct
21 Correct 45 ms 23372 KB Output is correct
22 Correct 485 ms 144744 KB Output is correct