Submission #816244

#	Time	Username	Problem	Language	Result	Execution time	Memory
816244		jophyyjh	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	519 ms	71392 KiB

crocodile

/**
 * Essentially a variant of Dijkstra's algorithm. The proof can be left as an exercise.
 * 
 * Time Complexity: O(n + m * log(m))           (Dijkstra)
 * Implementation 1                 (Full solution)
*/

#include <bits/stdc++.h>
#include "crocodile.h"

typedef long long   ll;
typedef std::vector<int>    vec;

const ll INF = 0x3f3f3f3f3f3f3f;


struct edge_t {
    int node, w;
};
typedef std::vector<edge_t> adj_list_t;

struct dist_info_t {
    int node;
    ll dist;
};

inline bool operator<(const dist_info_t& d1, const dist_info_t& d2) {
    return d1.dist > d2.dist;
}

int travel_plan(int n, int m, int edges[][2], int w[], int K, int P[]) {
    std::vector<adj_list_t> graph(n);
    for (int k = 0; k < m; k++) {
        graph[edges[k][0]].push_back(edge_t{edges[k][1], w[k]});
        graph[edges[k][1]].push_back(edge_t{edges[k][0], w[k]});
    }

    std::vector<ll> time(n, INF);
    std::priority_queue<dist_info_t> pq;
    vec wait(n, 2);
    for (int i = 0; i < K; i++) {
        time[P[i]] = 0, wait[P[i]] = 1;
        pq.push(dist_info_t{P[i], 0});
    }
    while (!pq.empty() && wait[0] > 0) {
        dist_info_t t = pq.top();
        pq.pop();
        if (wait[t.node] == 0)
            continue;
        time[t.node] = t.dist, wait[t.node]--;
        if (wait[t.node] == 0) {
            for (const edge_t& e : graph[t.node]) {
                if (wait[e.node] > 0)
                    pq.push(dist_info_t{e.node, time[t.node] + e.w});
            }
        }
    }
    assert(time[0] < INF);
    return time[0];
}

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