Submission #248509

#	Time	Username	Problem	Language	Result	Execution time	Memory
248509		A02	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	630 ms	94048 KiB

crocodile

#include "crocodile.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <utility>

using namespace std;

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

    vector<vector<pair<int, long long> > > adjacent (N, vector<pair<int, long long> >());

    for (int i = 0; i < M; i++){

        int s = R[i][0];
        int e = R[i][1];

        long long d = L[i];

        adjacent[s].push_back(make_pair(e, d));
        adjacent[e].push_back(make_pair(s, d));
    }

    vector<long long> max_escape (N, 1000000001);

    for (int i = 0; i < K; i++){
        max_escape[P[i]] = 0;
    }

    vector<long long> current_best_escape (N, 1000000001);
    vector<long long> current_second_best_escape (N, 1000000001);

    priority_queue<pair<int, long long> > to_visit;

    for (int i = 0; i < K; i++){

        int c_vertex = P[i];

        for (int j = 0; j < adjacent[c_vertex].size(); j++){

            int new_vertex = adjacent[c_vertex][j].first;
            long long escape_length = adjacent[c_vertex][j].second;

            if (escape_length <= current_best_escape[new_vertex]){
                current_second_best_escape[new_vertex] = current_best_escape[new_vertex];
                current_best_escape[new_vertex] = escape_length;
                to_visit.push(make_pair(-current_second_best_escape[new_vertex], new_vertex));
            } else{

                if (escape_length <= current_second_best_escape[new_vertex]){
                    current_second_best_escape[new_vertex] = escape_length;
                }
                to_visit.push(make_pair(-current_second_best_escape[new_vertex], new_vertex));

            }

        }

    }

    while (max_escape[0] == 1000000001){

        pair<long long, int> current_vertex_pair = to_visit.top();
        to_visit.pop();
        int c_vertex = current_vertex_pair.second;
        long long d = -current_vertex_pair.first;
        //cout << c_vertex << ' ' << d << endl;
        if (max_escape[c_vertex] == 1000000001){

            for (int j = 0; j < adjacent[c_vertex].size(); j++){

                int new_vertex = adjacent[c_vertex][j].first;
                long long escape_length = adjacent[c_vertex][j].second + d;

                if (escape_length <= current_best_escape[new_vertex]){
                    current_second_best_escape[new_vertex] = current_best_escape[new_vertex];
                    current_best_escape[new_vertex] = escape_length;
                    to_visit.push(make_pair(-current_second_best_escape[new_vertex], new_vertex));
                } else{

                    if (escape_length <= current_second_best_escape[new_vertex]){
                        current_second_best_escape[new_vertex] = escape_length;
                        to_visit.push(make_pair(-current_second_best_escape[new_vertex], new_vertex));
                    }

                }

            }

        }

        max_escape[c_vertex] = d;

    }

    return max_escape[0];
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:42:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < adjacent[c_vertex].size(); j++){
                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
crocodile.cpp:73:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < adjacent[c_vertex].size(); j++){
                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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