oj.uz

Submission #99525

# Submission time Handle Problem Language Result Execution time Memory
99525 2019-03-04T17:12:06 Z naoai Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 898 ms 52884 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long i64;
static const int nmax = 1e5;
static const i64 inf = 1LL << 60;

i64 d[nmax + 1];
i64 mn[nmax + 1][2];

struct str {
    int x;
    i64 val;

    str () {}
    str (int _x, i64 _val) {
        x = _x, val = _val;
    }

    bool operator < (const str &shp) const {
        return val > shp.val;
    }
};
priority_queue<str> h;

bool viz[nmax + 1];
vector<pair<int, int>> g[nmax + 1];

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

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

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

    while (!h.empty()) {
        str u = h.top();
        h.pop();

        if (viz[u.x] == 1)
            continue;
        viz[u.x] = 1;

        for (auto i : g[u.x]) {
            if (viz[i.first] == 1)
                continue;

            if (u.val + i.second <= mn[i.first][0]) {
                mn[i.first][1] = mn[i.first][0];
                mn[i.first][0] = u.val + i.second;
            } else if (u.val + i.second < mn[i.first][1]) {
                mn[i.first][1] = u.val + i.second;
            }

            if (mn[i.first][1] < d[i.first]) {
                d[i.first] = mn[i.first][1];
                h.push({i.first, d[i.first]});
            }
        }
    }

    return (int)d[0];
}

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 5 ms 2688 KB Output is correct
3 Correct 5 ms 2816 KB Output is correct
4 Correct 5 ms 2816 KB Output is correct
5 Correct 6 ms 2816 KB Output is correct
6 Correct 7 ms 2816 KB Output is correct
7 Correct 5 ms 2816 KB Output is correct
8 Correct 6 ms 2816 KB Output is correct
9 Correct 6 ms 3072 KB Output is correct
10 Correct 5 ms 2688 KB Output is correct
11 Correct 8 ms 2816 KB Output is correct
12 Correct 9 ms 3200 KB Output is correct
13 Correct 8 ms 3200 KB Output is correct
14 Correct 6 ms 2816 KB Output is correct
15 Correct 5 ms 2816 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 5 ms 2688 KB Output is correct
3 Correct 5 ms 2816 KB Output is correct
4 Correct 5 ms 2816 KB Output is correct
5 Correct 6 ms 2816 KB Output is correct
6 Correct 7 ms 2816 KB Output is correct
7 Correct 5 ms 2816 KB Output is correct
8 Correct 6 ms 2816 KB Output is correct
9 Correct 6 ms 3072 KB Output is correct
10 Correct 5 ms 2688 KB Output is correct
11 Correct 8 ms 2816 KB Output is correct
12 Correct 9 ms 3200 KB Output is correct
13 Correct 8 ms 3200 KB Output is correct
14 Correct 6 ms 2816 KB Output is correct
15 Correct 5 ms 2816 KB Output is correct
16 Correct 828 ms 46912 KB Output is correct
17 Correct 108 ms 15480 KB Output is correct
18 Correct 135 ms 16860 KB Output is correct
19 Correct 898 ms 52884 KB Output is correct
20 Correct 349 ms 40776 KB Output is correct
21 Correct 55 ms 8440 KB Output is correct
22 Correct 459 ms 36472 KB Output is correct