Submission #630424

#	Time	Username	Problem	Language	Result	Execution time	Memory
630424		NintsiChkhaidze	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	506 ms	77596 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define s second
#define pb push_back
#define ll long long
#define f first
 
const int nn = 300005;
vector <pair<int,ll> > v[nn];
pair<ll,ll> dis[nn];
 
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    for (int i = 0; i < M; i++){
        v[R[i][0]].pb({R[i][1],L[i]});
        v[R[i][1]].pb({R[i][0],L[i]});
    }
    for (int i=0;i<N; i++)
        dis[i] = {1e18,1e18};
 
    using T = pair<ll,int>;
    priority_queue <T, vector <T>, greater <T>> pq;
    for (int i = 0; i < K; i++)
        dis[P[i]] = {0LL,0LL},pq.push({0LL,P[i]});
 
    while(pq.size()){
        ll d = pq.top().f;
        int x = pq.top().s;
        pq.pop();
        if (d != dis[x].s) continue;
        for (auto [to,w]: v[x]){
            ll vl = w + d;
            ll old = dis[to].s;
            if (dis[to].f > vl) {
                dis[to].s = dis[to].f;
                dis[to].f = vl;
            }else if (dis[to].s > vl){
                dis[to].s = vl;
            }
            if (dis[to].s < old) pq.push({dis[to].s, to});
        }
    }
    return dis[0].s;
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:31:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |         for (auto [to,w]: v[x]){
      |                   ^

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