Submission #468264

#	Time	Username	Problem	Language	Result	Execution time	Memory
468264		alextodoran	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	938 ms	95924 KiB

crocodile

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

#include "crocodile.h"

using namespace std;

typedef long long ll;

const ll INF = LLONG_MAX / 2;

struct Edge
{
    int to;
    ll len;
};

struct Path
{
    int to;
    ll len;
};

bool operator < (const Path &p1, const Path &p2)
{
    return p1.len > p2.len;
}

int travel_plan (int N, int M, int R[][2], int L[], int K, int P[])
{
    vector <vector <Edge>> adj (N);
    for(int i = 0; i < M; i++)
    {
        adj[R[i][0]].push_back(Edge{R[i][1], L[i]});
        adj[R[i][1]].push_back(Edge{R[i][0], L[i]});
    }

    vector <bool> visited (N, false);
    vector <ll> dist1 (N, INF);
    vector <ll> dist2 (N, INF);

    priority_queue <Path> q;

    for(int i = 0; i < K; i++)
    {
        dist1[P[i]] = dist2[P[i]] = 0;
        q.push(Path{P[i], 0});
    }

    while(q.empty() == false)
    {
        Path p = q.top();
        q.pop();

        if(visited[p.to] == true)
            continue;

        visited[p.to] = true;

        for(Edge e : adj[p.to])
            if(visited[e.to] == false)
            {
                if(dist2[p.to] + e.len <= dist1[e.to])
                {
                    dist2[e.to] = dist1[e.to];
                    dist1[e.to] = dist2[p.to] + e.len;
                }
                else if(dist2[p.to] + e.len < dist2[e.to])
                {
                    dist2[e.to] = dist2[p.to] + e.len;
                }

                if(dist2[e.to] != INF)
                    q.push(Path{e.to, dist2[e.to]});
            }
    }

    return dist2[0];
}

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