Submission #497256

#	Time	Username	Problem	Language	Result	Execution time	Memory
497256		Leo121	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	1218 ms	101072 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, ll> pii;
struct ura{
    int inicio, destino;
    ll peso;
    const bool operator < (const ura & a) const {
        return peso > a.peso;
    }
};
priority_queue<ura> pq;
bool salidas[100002];
bool primer_camino[100002];
ll respuesta[100002];
vector<pii> graph[100002];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    forn(i, 0, N - 1){
        salidas[i] = 0;
        primer_camino[i] = 0;
        respuesta[i] = 0LL;
    }
    forn(i, 0, M - 1){
        graph[R[i][0]].pb(mp(R[i][1], (ll) L[i]));
        graph[R[i][1]].pb(mp(R[i][0], (ll) L[i]));
    }
    forn(i, 0, K - 1){
        primer_camino[P[i]] = 1;
        salidas[P[i]] = 1;
        for(pii u : graph[P[i]]){
            pq.push({P[i], u.fi, u.se});
        }
    }
    while(!pq.empty()){
        ura act = pq.top();
        pq.pop();
        if(salidas[act.destino]){
            continue;
        }
        if(!primer_camino[act.destino]){
            primer_camino[act.destino] = 1;
            continue;
        }
        salidas[act.destino] = 1;
        respuesta[act.destino] = act.peso;
        for(pii u : graph[act.destino]){
            pq.push({act.destino, u.fi, act.peso + u.se});
        }
    }
    return (int) respuesta[0];

}

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