Submission #764656

#	Time	Username	Problem	Language	Result	Execution time	Memory
764656		borisAngelov	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	855 ms	62848 KiB

crocodile

#include "crocodile.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

const int maxn = 100005;
const int inf = 1e9 + 5;

int n, m, k;

vector<pair<int, int>> g[maxn];

struct vertex
{
    int min1;
    int min2;
    int node;

    friend bool operator < (const vertex& a, const vertex& b)
    {
        return a.min2 < b.min2 || (a.min2 == b.min2 && a.node < b.node);
    }
};

set<vertex> s;

bool visited[maxn];

int dist[maxn];
int dist2[maxn];

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

    for (int i = 0; i < m; ++i)
    {
        int x = R[i][0];
        int y = R[i][1];
        int w = L[i];

        ++x;
        ++y;

        g[x].push_back(make_pair(y, w));
        g[y].push_back(make_pair(x, w));
    }

    for (int i = 1; i <= n; ++i)
    {
        dist[i] = inf;
        dist2[i] = inf;
    }

    for (int i = 0; i < k; ++i)
    {
        dist[P[i] + 1] = 0;
        dist2[P[i] + 1] = 0;
    }

    for (int i = 1; i <= n; ++i)
    {
        s.insert({dist[i], dist2[i], i});
    }

    while (!s.empty())
    {
        auto [best, second_best, node] = (*s.begin());

        s.erase(s.begin());

        if (visited[node] == true)
        {
            continue;
        }

        visited[node] = true;

        for (auto [next_node, w] : g[node])
        {
            if (visited[next_node] == false)
            {
                s.erase({dist[next_node], dist2[next_node], next_node});

                int new_dist = second_best + w;

                if (dist[next_node] > new_dist)
                {
                    dist2[next_node] = dist[next_node];
                    dist[next_node] = new_dist;
                }
                else if (dist2[next_node] > new_dist)
                {
                    dist2[next_node] = new_dist;
                }

                s.insert({dist[next_node], dist2[next_node], next_node});
            }
        }
    }

    return dist2[1];
}

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