Submission #43876

#	Time	Username	Problem	Language	Result	Execution time	Memory
43876		faustaadp	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	1431 ms	132084 KiB

crocodile

#include "crocodile.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll d[2][101010],i;
vector<ll> v[101010],w[101010];
priority_queue<pair<ll,ll> > pq;
pair<ll,ll> u;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	memset(d,-1,sizeof(d));
	for(i=0;i<M;i++)
	{
		v[R[i][0]].pb(R[i][1]);
		w[R[i][0]].pb(L[i]);
		v[R[i][1]].pb(R[i][0]);
		w[R[i][1]].pb(L[i]);
	}
	for(i=0;i<K;i++)
	{
		d[0][P[i]]=0;
		pq.push(mp(0,P[i]));
	}
	while(!pq.empty())
	{
		u=pq.top();
		pq.pop();
		if(d[0][u.se]==-1)
			d[0][u.se]=-u.fi;
		else
		if(d[1][u.se]==-1)
		{
			d[1][u.se]=-u.fi;
			for(i=0;i<v[u.se].size();i++)
				if(d[0][v[u.se][i]]==-1||d[1][v[u.se][i]]==-1)	
					pq.push(mp(u.fi-w[u.se][i],v[u.se][i]));
		}
	}
  	return d[1][0];
}

Compilation message (stderr)

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

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