oj.uz

Submission #104504

# Submission time Handle Problem Language Result Execution time Memory
104504 2019-04-07T08:53:01 Z dfistric Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 1637 ms 86392 KB 
#include <bits/stdc++.h>

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define ll long long
#define X first
#define Y second

using namespace std;

const int MAXN = 100100;
ll inf = (1LL << 60);
vector <pair <int, ll> > ve[MAXN];
int n, m;
ll A[MAXN], B[MAXN];
set <pair <ll, int> > se;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    n = N, m = M;

    REP(i, m) {
        int a = R[i][0], b = R[i][1];
        ll c = L[i];
        ve[a].push_back({b, c});
        ve[b].push_back({a, c});
    }

    REP(i, n) A[i] = B[i] = inf;
    REP(i, K) A[P[i]] = B[P[i]] = 0;
    REP(i, n) se.insert({B[i], i});

    while (se.size()) {
        auto tr = *se.begin();
        se.erase(se.begin());
        int x = tr.Y;
        for (auto t : ve[x]) {
            int y = t.X;
            ll d = tr.X + t.Y;

            if (d < B[y]) {
                se.erase({B[y], y});
                B[y] = d;
                if (A[y] > B[y]) swap(A[y], B[y]);
                se.insert({B[y], y});
            }
        }
    }


    return B[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 4 ms 2816 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 5 ms 2688 KB Output is correct
5 Correct 5 ms 2816 KB Output is correct
6 Correct 5 ms 2816 KB Output is correct
7 Correct 5 ms 2816 KB Output is correct
8 Correct 5 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 4 ms 2816 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 5 ms 2688 KB Output is correct
5 Correct 5 ms 2816 KB Output is correct
6 Correct 5 ms 2816 KB Output is correct
7 Correct 5 ms 2816 KB Output is correct
8 Correct 5 ms 2816 KB Output is correct
9 Correct 6 ms 3072 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct
11 Correct 6 ms 2860 KB Output is correct
12 Correct 9 ms 3328 KB Output is correct
13 Correct 7 ms 3456 KB Output is correct
14 Correct 5 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 4 ms 2816 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 5 ms 2688 KB Output is correct
5 Correct 5 ms 2816 KB Output is correct
6 Correct 5 ms 2816 KB Output is correct
7 Correct 5 ms 2816 KB Output is correct
8 Correct 5 ms 2816 KB Output is correct
9 Correct 6 ms 3072 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct
11 Correct 6 ms 2860 KB Output is correct
12 Correct 9 ms 3328 KB Output is correct
13 Correct 7 ms 3456 KB Output is correct
14 Correct 5 ms 2816 KB Output is correct
15 Correct 5 ms 2816 KB Output is correct
16 Correct 1020 ms 64560 KB Output is correct
17 Correct 178 ms 23928 KB Output is correct
18 Correct 320 ms 25720 KB Output is correct
19 Correct 1637 ms 86392 KB Output is correct
20 Correct 388 ms 67448 KB Output is correct
21 Correct 67 ms 11640 KB Output is correct
22 Correct 433 ms 65904 KB Output is correct