Submission #122249

#	Time	Username	Problem	Language	Result	Execution time	Memory
122249		joseacaz	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	1529 ms	121860 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
#define MAXN 100005
#define MAXM 1000005
#define INF (1LL << 60LL)

using namespace std;
typedef long long ll;

struct Nodes
{
    int node;
    ll a, b;

    bool operator < ( const Nodes& _x ) const
    {
        if ( b == _x.b )
        {
            if ( a == _x.a )
                return node > _x.node;
            return a > _x.a;
        }
        return b > _x.b;
    }
};

int N, M, K, R[MAXM][2], L[MAXM], P[MAXN], visited[MAXN];
ll A[MAXN], B[MAXN];
vector < pair < int, ll > > Graph[MAXN];
priority_queue < Nodes > PQ;

int travel_plan ( int n, int m, int r[][2], int l[], int k, int p[] )
{
    N = n;
    for ( int i = 0; i < N; i++ )
        A[i] = INF, B[i] = INF;
    M = m;
    for ( int i = 0; i < M; i++ )
        R[i][0] = r[i][0], R[i][1] = r[i][1], L[i] = l[i];
    K = k;
    for ( int i = 0; i < K; i++ )
        P[i] = p[i], PQ.push ( {P[i], 0, 0 } ), A[P[i]] = 0, B[P[i]] = 0;

    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]} );
    }

    while ( !PQ.empty() )
    {
        auto aux = PQ.top();
        PQ.pop();
        if ( visited[aux.node] )
            continue;
        visited[aux.node] = 1;

        for ( auto i : Graph[aux.node] )
        {
            ll tmp = i.second + B[aux.node];
            if ( tmp < A[i.first] )
                swap ( A[i.first], B[i.first] ), A[i.first] = tmp;
            else if ( tmp < B[i.first] )
                B[i.first] = tmp;

            if ( !visited[i.first] )
                PQ.push ( {i.first, A[i.first], B[i.first] } );
        }
    }

    return B[0];
}

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