Submission #764160

#	Time	Username	Problem	Language	Result	Execution time	Memory
764160		boris_mihov	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	857 ms	62928 KiB

crocodile

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

typedef long long llong;
const int MAXN = 100000 + 10;
const int INF  = 2e9;

struct Node
{
    int min;
    int min2;
    int node;

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

int n, m;
int min[MAXN];
int min2[MAXN];
int dist[MAXN];
bool vis[MAXN];
std::set <Node> s;
std::vector <std::pair <int,int>> g[MAXN];

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

    std::fill(min + 1, min + 1 + n, INF);
    std::fill(min2 + 1, min2 + 1 + n, INF);

    for (int i = 0 ; i < K ; ++i)
    {
        min[P[i] + 1] = min2[P[i] + 1] = 0;
    }

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

    while (!s.empty())
    {
        auto [currMIN, currDist, node] = (*s.begin());
        s.erase(s.begin());

        if (vis[node])
        {
            continue;
        }

        vis[node] = true;
        for (const auto &[u, dist] : g[node])
        {
            if (vis[u])
            {
                continue;
            }

            s.erase(s.find({min[u], min2[u], u}));
            if (min[u] > currDist + dist)
            {
                min2[u] = min[u];
                min[u] = currDist + dist;
            } else if (min2[u] > currDist + dist)
            {
                min2[u] = currDist + dist;
            }

            s.insert({min[u], min2[u], u});
        }
    }

    return min2[1];
}

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