Submission #420520

#	Time	Username	Problem	Language	Result	Execution time	Memory
420520		snasibov05	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	996 ms	102688 KiB

crocodile

#include "crocodile.h"
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

#define ll long long
#define pb push_back
#define pii pair<ll, ll>
#define f first;
#define s second;
#define oo 1000000000000000000ll

vector<vector<pii>> ed;
vector<bool> ext;
vector<int> visited;
vector<ll> res;

ll dijkstra(int n){
    vector<ll> dist1(n, oo), dist2(n, oo);
    vector<bool> visited(n);
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    for (int i = 0; i < n; ++i) {
        if (ext[i]) dist1[i] = dist2[i] = 0, pq.push({0, i});
    }

    while (!pq.empty()){
        int cur = pq.top().s;
        ll d = pq.top().f;
        pq.pop();

        if (visited[cur]) continue;

        visited[cur] = true;
        for (auto [to, l] : ed[cur]){
            if (visited[to]) continue;
            dist2[to] = min(dist2[to], d + l);
            if (dist1[to] > dist2[to]) swap(dist1[to], dist2[to]);
            pq.push({dist2[to], to});
        }
    }

    return dist2[0];
}

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){

    ed.resize(n);
    ext.resize(n);
    visited.resize(n);
    res.resize(n);

    for (int i = 0; i < m; ++i) {
        ed[r[i][0]].pb({r[i][1], l[i]});
        ed[r[i][1]].pb({r[i][0], l[i]});
    }

    for (int i = 0; i < k; ++i) {
        ext[p[i]] = true;
    }

    return (int)dijkstra(n);

}

Compilation message (stderr)

crocodile.cpp: In function 'long long int dijkstra(int)':
crocodile.cpp:37:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   37 |         for (auto [to, l] : ed[cur]){
      |                   ^

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