Submission #100554

#	Time	Username	Problem	Language	Result	Execution time	Memory
100554		alexpetrescu	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	695 ms	59972 KiB

crocodile

#include "crocodile.h"
#include <vector>

#define INF 1000000000
#define MAXN 100000

struct myc {
    int best, next;
    inline bool operator < (const myc &u) const {
        return next < u.next;
    }
} d[MAXN];

struct mom {
    int x, y;
};
std::vector < mom > g[MAXN];
int heap[MAXN + 1], poz[MAXN];
bool done[MAXN];

inline void mySwap(int p, int q) {
    int aux = heap[p];
    heap[p] = heap[q];
    heap[q] = aux;
    poz[heap[p]] = p;
    poz[heap[q]] = q;
}

inline void urcare(int p) {
    while (p > 1 && d[heap[p]] < d[heap[p / 2]]) {
        mySwap(p, p / 2);
        p /= 2;
    }
}

inline void coborare(int p) {
    int q;
    bool f = 1;
    while (f && (q = 2 * p) <= heap[0]) {
        if (q < heap[0] && d[heap[q + 1]] < d[heap[q]])
            q++;
        if (d[heap[q]] < d[heap[p]]) {
            mySwap(p, q);
            p = q;
        } else
            f = 0;
    }
}

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++) d[i] = {INF, INF}, done[i] = 0;
    for (int i = 0; i < K; i++) d[P[i]] = {0, 0};
    for (int i = 0; i < N; i++) heap[i + 1] = i, poz[i] = i + 1;
    heap[0] = N;
    for (int i = N; i > 0; i--)
        coborare(i);
    while (heap[1] != 0) {
        int x = heap[1];
        done[x] = 1;
        for (auto &y : g[x]) {
            if (done[y.x] == 0) {
                long long val = d[x].next + y.y;
                if (val < d[y.x].next) {
                    if (val < d[y.x].best) {
                        d[y.x].next = d[y.x].best;
                        d[y.x].best = val;
                    } else
                        d[y.x].next = val;
                    urcare(poz[y.x]);
                }
            }
        }
        d[x] = {INF, INF};
        coborare(1);
    }
    return d[0].next;
}

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11