oj.uz

Submission #182612

# Submission time Handle Problem Language Result Execution time Memory
182612 2020-01-10T02:44:07 Z tri Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 826 ms 88476 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

typedef pair<pl, int> state;

#define pb push_back
#define f first
#define s second

namespace debug {
    const int DEBUG = true;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"), cout << flush; }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;

const int MAXN = 1e6 + 100;
const ll INF = 1e15;

int vis[MAXN];

pl bTimes[MAXN];
ll eTime[MAXN];

bool update(pl &p, int x) {
    if (x <= p.s) {
        p.f = p.s;
        p.s = x;
        return p.f != INF;
    }
    if (x <= p.f) {
        p.f = x;
        return true;
    }
    return false;
}

vector<pi> aL[MAXN];

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

    priority_queue<state, vector<state>, greater<state>> queue;

    for (int i = 0; i < N; i++) {
        vis[i] = false;
        bTimes[i] = {INF, INF};
        eTime[i] = INF;
    }

    for (int i = 0; i < K; i++) {
        int cV = P[i];
        vis[cV] = true;
        eTime[cV] = 0;

        for (pi aE : aL[cV]) {
            int aV = aE.f;
            if (!vis[aV]) {
                ll nxtTime = eTime[cV] + aE.s;
                if (update(bTimes[aV], nxtTime)) {
                    queue.push({{bTimes[aV]}, aV});
                }
            }
        }
    }

    while (!queue.empty()) {
        state cState = queue.top();
        queue.pop();

        int cV = cState.s;
        if (vis[cV]) {
            continue;
        }
        vis[cV] = true;

        eTime[cV] = cState.f.f;

        for (pi aE : aL[cV]) {
            int aV = aE.f;
            if (!vis[aV]) {
                ll nxtTime = eTime[cV] + aE.s;
                if (update(bTimes[aV], nxtTime)) {
                    queue.push({{bTimes[aV]}, aV});
                }
            }
        }
    }

    return eTime[0];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 24 ms 23800 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 25 ms 23928 KB Output is correct
5 Correct 25 ms 23928 KB Output is correct
6 Correct 25 ms 23928 KB Output is correct
7 Correct 25 ms 23928 KB Output is correct
8 Correct 25 ms 24024 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 24 ms 23800 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 25 ms 23928 KB Output is correct
5 Correct 25 ms 23928 KB Output is correct
6 Correct 25 ms 23928 KB Output is correct
7 Correct 25 ms 23928 KB Output is correct
8 Correct 25 ms 24024 KB Output is correct
9 Correct 26 ms 24184 KB Output is correct
10 Correct 24 ms 23932 KB Output is correct
11 Correct 25 ms 23928 KB Output is correct
12 Correct 28 ms 24440 KB Output is correct
13 Correct 27 ms 24440 KB Output is correct
14 Correct 24 ms 23928 KB Output is correct
15 Correct 24 ms 23928 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 24 ms 23800 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 25 ms 23928 KB Output is correct
5 Correct 25 ms 23928 KB Output is correct
6 Correct 25 ms 23928 KB Output is correct
7 Correct 25 ms 23928 KB Output is correct
8 Correct 25 ms 24024 KB Output is correct
9 Correct 26 ms 24184 KB Output is correct
10 Correct 24 ms 23932 KB Output is correct
11 Correct 25 ms 23928 KB Output is correct
12 Correct 28 ms 24440 KB Output is correct
13 Correct 27 ms 24440 KB Output is correct
14 Correct 24 ms 23928 KB Output is correct
15 Correct 24 ms 23928 KB Output is correct
16 Correct 647 ms 81188 KB Output is correct
17 Correct 121 ms 36856 KB Output is correct
18 Correct 181 ms 38360 KB Output is correct
19 Correct 826 ms 88476 KB Output is correct
20 Correct 377 ms 70936 KB Output is correct
21 Correct 72 ms 29432 KB Output is correct
22 Correct 438 ms 67960 KB Output is correct