oj.uz

Submission #951014

# Submission time Handle Problem Language Result Execution time Memory
951014 2024-03-21T04:15:30 Z efishel Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 819 ms 123048 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;

const ll MAXN = 1E5+16;
vector <pair <ll, ll> > adj[MAXN];

int travel_plan (int _n, int _m, int _r[][2], int _l[], int _k, int _p[]) {
    ll n = _n, m = _m, k = _k;
    for (ll i = 0; i < m; i++) {
        ll u = _r[i][0], v = _r[i][1];
        ll w = _l[i];
        adj[u].push_back({ v, w });
        adj[v].push_back({ u, w });
    }
    priority_queue <pair <ll, ll> > pq;
    vll cvis(n, 0);
    vector <bool> vis(n, false);
    vll dis(n);
    vll srcs(_p, _p+k);
    for (ll u : srcs) {
        cvis[u] = 1;
        dis[u] = 0;
        pq.push({ -dis[u], u });
    }
    while (pq.size()) {
        auto [disU, u] = pq.top(); disU = -disU; pq.pop();
        cvis[u]++;
        if (cvis[u] != 2) continue;
        dis[u] = disU;
        for (auto [v, w] : adj[u]) {
            pq.push({ -(dis[u]+w), v });
        }
    }
    return int(dis[0]);
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6776 KB Output is correct
4 Correct 2 ms 6744 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6812 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6776 KB Output is correct
4 Correct 2 ms 6744 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6812 KB Output is correct
9 Correct 4 ms 7512 KB Output is correct
10 Correct 1 ms 6748 KB Output is correct
11 Correct 2 ms 6788 KB Output is correct
12 Correct 6 ms 7904 KB Output is correct
13 Correct 6 ms 7908 KB Output is correct
14 Correct 2 ms 6748 KB Output is correct
15 Correct 2 ms 6744 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6776 KB Output is correct
4 Correct 2 ms 6744 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6812 KB Output is correct
9 Correct 4 ms 7512 KB Output is correct
10 Correct 1 ms 6748 KB Output is correct
11 Correct 2 ms 6788 KB Output is correct
12 Correct 6 ms 7904 KB Output is correct
13 Correct 6 ms 7908 KB Output is correct
14 Correct 2 ms 6748 KB Output is correct
15 Correct 2 ms 6744 KB Output is correct
16 Correct 738 ms 118468 KB Output is correct
17 Correct 62 ms 19284 KB Output is correct
18 Correct 88 ms 23836 KB Output is correct
19 Correct 819 ms 123048 KB Output is correct
20 Correct 515 ms 105712 KB Output is correct
21 Correct 34 ms 12628 KB Output is correct
22 Correct 435 ms 66760 KB Output is correct