Submission #93989

#	Time	Username	Problem	Language	Result	Execution time	Memory
93989		someone_aa	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	668 ms	68360 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
ll distf[maxn], dists[maxn];
vector<pair<int,int> > g[maxn];
bool f[maxn], visited[maxn];

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]].pb(mp(R[i][1], L[i]));
        g[R[i][1]].pb(mp(R[i][0], L[i]));
    }

    for(int i=0;i<K;i++) {
        f[P[i]] = true;
    }

    priority_queue<pll, vector<pll>, greater<pll> > pq;

    for(int i=0;i<N;i++) {
        if(f[i]) {
            distf[i] = dists[i] = 0;
            pq.push(mp(0, i));
        }
        else {
            distf[i] = dists[i] = INT_MAX;
        }
    }

    while(!pq.empty()) {
        pll curr = pq.top();
        pq.pop();

        if(visited[curr.second]) continue;
        visited[curr.second] = true;

        if(curr.second == 0) {
            return dists[curr.second];
        }

        int node = curr.second;

        for(auto i:g[node]) {
            if(!visited[i.first]) {
                ll extended = dists[node] + i.second;

                if(extended < distf[i.first]) {
                    dists[i.first] = distf[i.first];
                    distf[i.first] = extended;
                    pq.push(mp(dists[i.first], i.first));
                }
                else if(extended < dists[i.first]) {
                    dists[i.first] = extended;
                    pq.push(mp(dists[i.first], i.first));
                }
            }
        }
    }
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:64:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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