Submission #630412

#	Time	Username	Problem	Language	Result	Execution time	Memory
630412		NintsiChkhaidze	Crocodile's Underground City (IOI11_crocodile)	C++14	89 / 100	554 ms	77144 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 = 100005;
vector <pair<int,ll> > v[nn];
pair<ll,ll> dis[nn];
bool vis[nn];

// int R[nn][4],L[nn],P[nn];
// int main (){
//     int N,M,K;
//     cin>>N>>M>>K;
    
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;
        vis[x] = 1;
        for (auto [to,w]: v[x]){
            if (vis[to]) continue;
            int vl = w + d;
            if (dis[to].f > vl) {
                dis[to].s = dis[to].f;
                dis[to].f = vl;
                pq.push({dis[to].s, to});
            }else if (dis[to].s > vl){
                dis[to].s = vl;
                pq.push({dis[to].s, to});
            }
            
        }
    }

    return dis[0].s;
    // cout<<dis[0].s;
}
 
 

Compilation message (stderr)

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

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