Submission #852328

#	Time	Username	Problem	Language	Result	Execution time	Memory
852328		uped	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	1 ms	4440 KiB

crocodile

#include "crocodile.h"

#include <bits/stdc++.h>

using namespace std;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    vector<vector<pair<int, int>>> adj(N);
    for (int i = 0; i < M; ++i) {
        adj[R[i][0]].emplace_back(R[i][1], L[i]);
        adj[R[i][1]].emplace_back(R[i][0], L[i]);
    }
    vector<bool> is_exit(N);
    for (int i = 0; i < K; ++i) {
        is_exit[P[i]] = true;
    }

    priority_queue<pair<int, int>> pq;
    vector<int> distance(N, INT32_MAX);
    pq.emplace(0, 0);
    distance[0] = 0;
    int ans = INT32_MAX;
    while (!pq.empty()) {
        auto [dist, a] = pq.top(); pq.pop();
        if (-dist != distance[a]) continue;

        pair<int,int> min {-1, -1};
        for (auto [b, w] : adj[a]) {
            if (is_exit[b]) {
                if (min.first == -1 || w < min.first) {
                    min.second = min.first;
                    min.first = w;
                } else if (min.second == -1 || w < min.second) {
                    min.second = w;
                }
            } else if (distance[a] + w < distance[b]) {
                distance[b] = distance[a] + w;
                pq.emplace(-distance[b], b);
            }
        }
        if (min.second != -1) {
            ans = ::min(ans, distance[a] + min.second);
        }
    }
    return ans;
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:24:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |         auto [dist, a] = pq.top(); pq.pop();
      |              ^
crocodile.cpp:28:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |         for (auto [b, w] : adj[a]) {
      |                   ^

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