Submission #497246

#	Time	Username	Problem	Language	Result	Execution time	Memory
497246		Ozy	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	1716 ms	133292 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 100000
#define des first
#define peso second

lli n,m,a,b,res;
vector<pair<lli,lli> > hijos[MAX+2];
lli visitados[MAX+2];
set<pair<lli,lli> > cola;
set<pair<lli,lli> >::iterator it;
pair<lli,lli> act;
multiset<lli> llegadas[MAX+2];
multiset<lli>::iterator ot;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{

    n = N;
    m = M;
    rep(i,0,m-1) {
        a = R[i][0];
        b = R[i][1];
        hijos[a].push_back({b,L[i]});
        hijos[b].push_back({a,L[i]});
    }

    rep(i,0,K-1) {
        a = P[i];
        cola.insert({0,a});
    }

    while (!cola.empty()) {

        it = cola.begin();
        act = (*it);
        cola.erase(it);

        if (visitados[act.second] == 1) continue;
        visitados[act.second] = 1;

        if (act.second == 0) {
            res = act.first;
            break;
        }

        for (auto h : hijos[act.second]) {
            if (visitados[h.des] == 1) continue;

            a = act.first + h.peso;
            llegadas[h.des].insert(a);

            if (llegadas[h.des].size() > 1)  {

                ot = llegadas[h.des].begin();
                ot++;
                a = (*ot);
                if (cola.find({a,h.des}) == cola.end()) cola.insert({a,h.des});

            }

        }

    }

    return res;
}

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