Submission #51992

#	Time	Username	Problem	Language	Result	Execution time	Memory
51992		gs13105	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	785 ms	46104 KiB

crocodile

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <iterator>

using namespace std;

struct edg
{
    int x, w;
    bool operator <(const edg &a) const
    {
        return w > a.w;
    }
};

vector<edg> arr[100010];
edg dis[100010][2];
int INF = 1e9 + 10;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    for(int i = 0; i < M; i++)
    {
        int x = R[i][0];
        int y = R[i][1];
        int w = L[i];
        arr[x].push_back({ y, w });
        arr[y].push_back({ x, w });
    }

    for(int i = 0; i < N; i++)
        dis[i][0] = dis[i][1] = { i, INF };

    priority_queue<edg> pq;
    for(int i = 0; i < K; i++)
    {
        int x = P[i];
        dis[x][0] = dis[x][1] = { x, 0 };
        pq.push({ x, 0 });
    }

    while(!pq.empty())
    {
        int x = pq.top().x;
        int w = pq.top().w;
        pq.pop();

        if(w > dis[x][1].w)
            continue;

        for(edg e : arr[x])
        {
            int nw = w + e.w;
            if(nw < dis[e.x][0].w)
            {
                if(x == dis[e.x][0].x)
                    dis[e.x][0].w = nw;
                else
                {
                    dis[e.x][1] = dis[e.x][0];
                    dis[e.x][0] = { x, nw };
                    if(dis[e.x][1].w != INF)
                        pq.push({ e.x, dis[e.x][1].w });
                }
            }
            else if(nw < dis[e.x][1].w && x != dis[e.x][0].x)
            {
                dis[e.x][1] = { x, nw };
                if(dis[e.x][1].w != INF)
                    pq.push({ e.x, dis[e.x][1].w });
            }
        }
    }

    assert(dis[0][1].w != INF);
    return dis[0][1].w;
}

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