oj.uz

Submission #248491

# Submission time Handle Problem Language Result Execution time Memory
248491 2020-07-12T14:31:27 Z A02 Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 1180 ms 262148 KB 
#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;
            } 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;
        max_escape[c_vertex] = d;
        //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;
                } 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));

            }

        }

    }

    return max_escape[0];
}

Compilation message

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

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Runtime error 1180 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Runtime error 1180 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1180 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -