Submission #1232967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232967		imann	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	266 ms	48648 KiB

crocodile

#include <iostream>
#include <vector>
#include <array>
#include <queue>
#include <limits>
#include <algorithm>

using ll = long long;

const int MAX_N = 100*1000 + 2;

std::array<std::vector<std::pair<int, int>>, MAX_N> graph;
std::array<bool, MAX_N> visit;

ll travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
    for (int i = 0; i < m; ++i) {
        graph[r[i][0]].push_back({r[i][1], l[i]});
        graph[r[i][1]].push_back({r[i][0], l[i]});
    }

    using T = std::pair<ll, ll>;
    std::priority_queue<T, std::vector<T>, std::greater<T>> pq;
    std::array<ll, MAX_N> dist;
    dist.fill({std::numeric_limits<int>::max()});
    for (int i = 0; i < k; ++i) {
        pq.push({0, p[i]});
        dist[p[i]] = 0;
    }
    std::array<std::pair<ll, ll>, MAX_N> mins;
    mins.fill({std::numeric_limits<int>::max(), std::numeric_limits<int>::max()});
    while (!pq.empty()) {
        auto [d, node] = pq.top();
        pq.pop();
        if (d == std::numeric_limits<int>::max()) {
            break;
        }
        if (d != dist[node])
            continue;
        if (visit[node])
            continue;
        visit[node] = true;
        for (std::pair<int, int> nei : graph[node]) {
            if (dist[nei.first] > d + nei.second) {
                std::vector<ll> minOpts = {d + nei.second, mins[nei.first].first, mins[nei.first].second};
                std::sort(minOpts.begin(), minOpts.end());
                mins[nei.first] = {minOpts[0], minOpts[1]};
                if (minOpts[1] != std::numeric_limits<int>::max()) {
                    dist[nei.first] = minOpts[1];
                    pq.push({dist[nei.first], nei.first});
                }
            }
        }
    }
    return dist[0];
}

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