Submission #402706

#	Time	Username	Problem	Language	Result	Execution time	Memory
402706		Antekb	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	817 ms	61560 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define mp(x, y) make_pair(x ,y)
typedef long long ll;
const ll INF=1e18;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	ll dist[N], dist2[N];
	vector<pair<int, int> > E[N];
	for(int i=0; i<M; i++){
		E[R[i][0]].push_back(mp(R[i][1], L[i]));
		E[R[i][1]].push_back(mp(R[i][0], L[i]));
	}
	for(int i=0; i<N;i++)dist[i]=dist2[i]=INF;
	for(int i=0; i<K; i++)dist[P[i]]=dist2[P[i]]=0;
	set<pair<ll, int> > S;
	for(int i=0;i<N; i++){
		S.insert(mp(dist[i], i));
	}
	while(S.size()){
		int v=(*S.begin()).nd;
		S.erase(S.begin());
		if(v==0){
			return dist[v];
		}
		for(auto i:E[v]){
			if(dist[v]+i.nd<dist[i.st]){
				S.erase(S.find(mp(dist[i.st], i.st)));
				if(dist[v]+i.nd>dist2[i.st])dist[i.st]=dist[v]+i.nd;
				else{
					dist[i.st]=dist2[i.st];
					dist2[i.st]=dist[v]+i.nd;
				}
				S.insert(mp(dist[i.st], i.st));
			}
		}
	}
}

Compilation message (stderr)

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

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