Submission #272748

#	Time	Username	Problem	Language	Result	Execution time	Memory
272748		toonewbie	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	670 ms	88736 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"

using namespace std;

const int N = 100005;

vector <pair <int, int>> g[N];
int used[N];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
    for (int i = 0; i < M; i++) {
        g[R[i][0]].push_back({R[i][1], L[i]});
        g[R[i][1]].push_back({R[i][0], L[i]});
    }
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    for (int i = 0; i < K; i++) {
        pq.push({0, P[i]});
        used[P[i]] = 1;
    }
    while(!pq.empty()) {
        auto cur = pq.top(); pq.pop();
        long long d = cur.first; int v = cur.second;
        if (++used[v] != 2) continue;
        if (v == 0) {
            return d;
        }
        for (auto i : g[v]) {
            pq.push({d + i.second, i.first});
        }
    }
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:16:103: warning: control reaches end of non-void function [-Wreturn-type]
   16 |     priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
      |                                                                                                       ^~

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