Submission #1250575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250575		pramad712	Crocodile's Underground City (IOI11_crocodile)	C++20	100 / 100	400 ms	50884 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;

#define INFINITY 2'000'000'010

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    int node_count = N, edge_count = M;
    auto edges = R; auto weights = L;
    int exit_count = K; auto exits = P;

    vector<vector<pair<int, int>>> graph(node_count);

    for (int index = 0; index < edge_count; index++) {
        auto [first, second] = edges[index];
        int weight = weights[index];

        graph[first].emplace_back(second, weight);
        graph[second].emplace_back(first, weight);
    }

    vector distances(node_count, make_pair(INFINITY, INFINITY));
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> djikstra;

    for (int index = 0; index < exit_count; index++) {
        djikstra.emplace(0, exits[index]);
        djikstra.emplace(0, exits[index]);
    }

    while (!djikstra.empty()) {
        auto [distance, node] = djikstra.top();
        djikstra.pop();

        if (distance < distances[node].first) {
            distances[node].first = distance;
            continue;
        }

        if (distance < distances[node].second) {
            distances[node].second = distance;
        }

        else {
            continue;
        }

        for (auto [adjacent, weight]: graph[node]) {
            if (distances[adjacent].second == INFINITY) {
                djikstra.emplace(distance + weight, adjacent);
            }
        }
    }

    return distances[0].second;
}

// #define MAX_N 50000
// #define MAX_M 10000000
//
// static int N, M;
// static int R[MAX_M][2];
// static int L[MAX_M];
// static int K;
// static int P[MAX_N];
// static int solution;
//
// inline
// void my_assert(int e) {if (!e) abort();}
//
// int main() {
//   int i;
//   my_assert(3==scanf("%d %d %d",&N,&M,&K));
//   for(i=0; i<M; i++)
//     my_assert(3==scanf("%d %d %d",&R[i][0],&R[i][1],&L[i]));
//   for(i=0; i<K; i++)
//     my_assert(1==scanf("%d",&P[i]));
//   my_assert(1==scanf("%d",&solution));
//
//   int ans = travel_plan(N,M,R,L,K,P);
//   cout << ans << "\n";
// }

Compilation message (stderr)

crocodile.cpp:5: warning: "INFINITY" redefined
    5 | #define INFINITY 2'000'000'010
      | 
In file included from /usr/include/c++/11/cmath:45,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from crocodile.cpp:2:
/usr/include/math.h:91: note: this is the location of the previous definition
   91 | #  define INFINITY (__builtin_inff ())
      |

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