oj.uz

Submission #910997

# Submission time Handle Problem Language Result Execution time Memory
910997 2024-01-18T10:56:41 Z Ghetto Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 956 ms 125096 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pil = pair<int, lint>;
using pli = pair<lint, int>;
static const int MAX_N = 1e5 + 5;

// Check program not run multiple times
static int n, m;
static vector<pil> adj[MAX_N];
static int k;
static bool is_exit[MAX_N];

static int seen[MAX_N];
static lint dist[MAX_N];
static priority_queue<pli, vector<pli>, greater<pli>> order;
lint dijk() {
    for (int i = 0; i < n; i++) {
        if (!is_exit[i]) continue;
        seen[i] = 1;
        order.push({0, i});
    }

    while (order.size()) {
        int u = order.top().second;
        lint d = order.top().first;
        order.pop();

        if (seen[u] == 0) {
            seen[u] = 1;
            continue;
        } else if (seen[u] == 1) {
            seen[u] = 2;
            dist[u] = d;
        } else continue;

        for (pil e : adj[u]) {
            lint new_dist = e.second + dist[u];
            order.push({new_dist, e.first});
        }
    }

    return dist[0];
}

int travel_plan(int tmp_n, int tmp_m, int tmp_r[][2], int tmp_l[], int tmp_k, int tmp_p[]) {
    n = tmp_n;
    m = tmp_m;
    for (int i = 0; i < m; i++) {
        int u = tmp_r[i][0], v = tmp_r[i][1];
        lint w = tmp_l[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    k = tmp_k;
    for (int i = 0; i < k; i++)
        is_exit[tmp_p[i]] = true;
    
    lint ans = dijk();
    return ans;
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 3 ms 8616 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 3 ms 8616 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 4 ms 9308 KB Output is correct
10 Correct 2 ms 8536 KB Output is correct
11 Correct 3 ms 8796 KB Output is correct
12 Correct 7 ms 9696 KB Output is correct
13 Correct 6 ms 9928 KB Output is correct
14 Correct 2 ms 8536 KB Output is correct
15 Correct 3 ms 8792 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 3 ms 8616 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 4 ms 9308 KB Output is correct
10 Correct 2 ms 8536 KB Output is correct
11 Correct 3 ms 8796 KB Output is correct
12 Correct 7 ms 9696 KB Output is correct
13 Correct 6 ms 9928 KB Output is correct
14 Correct 2 ms 8536 KB Output is correct
15 Correct 3 ms 8792 KB Output is correct
16 Correct 889 ms 121452 KB Output is correct
17 Correct 69 ms 23800 KB Output is correct
18 Correct 111 ms 26140 KB Output is correct
19 Correct 956 ms 125096 KB Output is correct
20 Correct 509 ms 107724 KB Output is correct
21 Correct 38 ms 16240 KB Output is correct
22 Correct 463 ms 72608 KB Output is correct