Submission #547081

#	Time	Username	Problem	Language	Result	Execution time	Memory
547081		Hanksburger	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	586 ms	93448 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<long long, long long> > adj[100005];
priority_queue<pair<long long, long long> > pq;
long long dist[100005], dist2[100005];
bool visited[100005];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	for (long long i=0; i<M; i++)
	{
		long long u=R[i][0], v=R[i][1], w=L[i];
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	for (long long i=0; i<N; i++)
		dist[i]=dist2[i]=1e18;
	for (long long i=0; i<K; i++)
	{
		long long u=P[i];
		dist[u]=dist2[u]=0;
		pq.push({0, u});
	}
	while (!pq.empty())
	{
		long long u=pq.top().second;
		pq.pop();
		if (visited[u])
			continue;
		visited[u]=1;
		for (long long i=0; i<adj[u].size(); i++)
		{
			long long v=adj[u][i].first, w=adj[u][i].second;
			if (dist[v]>dist2[u]+w)
			{
				dist2[v]=dist[v];
				dist[v]=dist2[u]+w;
				pq.push({-dist2[v], v});
			}
			else if (dist2[v]>dist2[u]+w)
			{
				dist2[v]=dist2[u]+w;
				pq.push({-dist2[v], v});
			}
		}
	}
	return dist2[0];
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:31:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for (long long i=0; i<adj[u].size(); i++)
      |                       ~^~~~~~~~~~~~~~

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