Submission #249741

#	Time	Username	Problem	Language	Result	Execution time	Memory
249741		eohomegrownapps	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	739 ms	97500 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<pair<ll,ll>>> adjlist; //val,node
ll n,k;
vector<ll> exits; //k of them
ll INF = 1e18;
ll dijkstra(){
    //source is 0
    vector<pair<ll,ll>> distances(n,{INF,INF}); //second then first
    priority_queue<pair<pair<ll,ll>,ll>,vector<pair<pair<ll,ll>,ll>>,greater<pair<pair<ll,ll>,ll>>> pq;
    //second,first
    for (ll i = 0; i<k; i++){
        distances[exits[i]]={0,0};
        pq.push({{0,0},exits[i]});
    }
    while (pq.size()>0){
        auto f = pq.top();
        pq.pop();
        /*cout<<"======\n";
        cout<<f.second<<'\n';
        for (auto p : distances){
            cout<<p.first<<" "<<p.second<<'\n';
        }*/
        //cout<<"check: "<<distances[f.second].first<<" "<<distances[f.second].second<<", "<<f.first.first<<" "<<f.first.second<<'\n';
        if (distances[f.second]<f.first){
            continue; //can't remember this condition
        }
        for (auto p : adjlist[f.second]){
            ll dist = p.first;
            ll node = p.second;
            ll newval = distances[f.second].first+dist;
            //cout<<newval<<'\n';
            if (newval<=distances[node].second){
                distances[node].first=distances[node].second;
                distances[node].second=newval;
                pq.push({distances[node],node});
            } else if (newval<distances[node].first){
                distances[node].first=newval;
                pq.push({distances[node],node});
            }
        }
    }
    return distances[0].first;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    n=N;k=K;
    adjlist.resize(n);
    for (ll i = 0; i<M; i++){
        adjlist[R[i][0]].push_back({L[i],R[i][1]});
        adjlist[R[i][1]].push_back({L[i],R[i][0]});
    }
    exits = vector<ll>(P,P+k);
    return dijkstra();
}

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