Submission #157544

#	Time	Username	Problem	Language	Result	Execution time	Memory
157544		GioChkhaidze	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	1164 ms	98732 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int Nn=100005;
long long n,m,k,fix[Nn],D1[Nn],D2[Nn];
vector < pair < long long , long long > > v[Nn];
set < pair < long long , long long  > > st;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	n=N,m=M,k=K;
	
	for (int i=0; i<m; i++) {
		v[R[i][0]].push_back({R[i][1],L[i]});
		v[R[i][1]].push_back({R[i][0],L[i]});
	}
	
	for (int i=0; i<n; i++)
		D1[i]=1e18,D2[i]=1e18;
	
	for (int i=0; i<k; i++) {
		D1[P[i]]=0,D2[P[i]]=0;
		st.insert({D2[P[i]],P[i]});
	}
	
	while (st.size()) {
		int x=(*st.begin()).S;
		st.erase(st.find(*st.begin()));
		
		if (fix[x]) continue;
		fix[x]=1;
		
		for (int i=0; i<v[x].size(); i++) {
			int to=v[x][i].F,cost=v[x][i].S;
			if (D2[x]+cost<D1[to]) {
				D2[to]=D1[to];
				D1[to]=D2[x]+cost;
				st.insert({D2[to],to});
			}
				else 
			if (D2[x]+cost<D2[to]) {
				D2[to]=D2[x]+cost;
				st.insert({D2[to],to});
			}
		}
	}
	
	if (D2[0]==1e18) D2[0]=-1;
	return D2[0];
}

Compilation message (stderr)

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

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