Submission #112538

#	Time	Username	Problem	Language	Result	Execution time	Memory
112538		nxteru	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	822 ms	89280 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
ll n,m,k,d[100005],dd[100005];
vector<P>g[100005];
int travel_plan(int N, int M, int R[][2], int L[], int K, int T[]){
	n=N,m=M,k=K;
	for(int i=0;i<m;i++){
		ll a=R[i][0],b=R[i][1],c=L[i];
		g[a].PB(P(b,c));
		g[b].PB(P(a,c));
	}
	for(int i=0;i<n;i++)d[i]=INF,dd[i]=INF;
	priority_queue<P,vector<P>,greater<P> >dik;
	for(int i=0;i<k;i++){
		ll v=T[i];
		d[v]=0;
		dd[v]=0;
		dik.push(P(0,v));
	}
	while(!dik.empty()){
		ll c=dik.top().F,v=dik.top().S;
		dik.pop();
		if(dd[v]<c)continue;
		for(int i=0;i<g[v].size();i++){
			ll u=g[v][i].F,p=c+g[v][i].S;
			if(d[u]>p)swap(d[u],p);
			if(dd[u]>p){
				dd[u]=p;
				dik.push(P(p,u));
			}
		}
	}
	return dd[0];
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:31:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[v].size();i++){
               ~^~~~~~~~~~~~

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