Submission #207380

#	Time	Username	Problem	Language	Result	Execution time	Memory
207380		robs	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	1432 ms	58832 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
#define debug(args...) //fprintf(stderr, args)
#define mk make_pair
using namespace std;
const int maxn = 2e5, INF = 1e9;
int dist[maxn],distMin[maxn],marcExit[maxn],contExit[maxn],resp,n;
vector<int> grafo[maxn];
vector<int> peso[maxn];
vector<int> casos[maxn];
set<pair<int, int> > fora;

void dijkstra()
{
	debug("dijkstra\n");
	debug("set foi!!\n");
	debug("criei os set ai\n");
	for(int x = 0; x < n; x++)	fora.insert( mk(dist[x], x));
	debug("inicializei dnv\n");
	while(!fora.empty())
	{
		int cur = fora.begin()->second;
		debug("	%d:\n",cur);
		fora.erase(fora.begin());
		for(int x = 0; x < grafo[cur].size(); x++)
		{
			int viz = grafo[cur][x];
			debug("		%d\n",viz);
			int p = peso[cur][x];
			if(dist[cur] + p < distMin[viz])
			{
				fora.erase( mk(dist[viz], viz));
				dist[viz] = distMin[viz];
				distMin[viz] = dist[cur] + p;
				fora.insert( mk(dist[viz], viz));
				continue;
			}
			if(dist[cur] + p < dist[viz])
			{
				fora.erase( mk(dist[viz], viz));
				dist[viz] = dist[cur] + p;
				fora.insert( mk(dist[viz], viz));
			}
		}
	}
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	debug("comeco\n");
	n = N;
	for(int x = 0; x < K; x++)	marcExit[P[x]] = 1;
	for(int x = 0; x < M; x++)
	{
		int i = R[x][0];
		int j = R[x][1];
		int p = L[x];
		grafo[i].push_back(j);
		grafo[j].push_back(i);
		peso[i].push_back(p);
		peso[j].push_back(p);
		if(marcExit[i] && marcExit[j])	continue;
		if(marcExit[i])	contExit[j]++;
		if(marcExit[j])	contExit[i]++;
	}
	debug("criou o grafo\n");
	for(int x = 0; x < N; x++)
	{
		if(marcExit[x])
		{
			distMin[x] = 0;
			dist[x] = 0;
		}
		else
		{
			distMin[x] = INF;
			dist[x] = INF;
		}
		if(contExit[x] >= 2)
		{
			int Min = INF;
			int Max = INF;
			for(int y = 0; y < grafo[x].size(); y++)
			{
				int viz = grafo[x][y];
				int p = peso[x][y];
				if(dist[viz] + p < Min)
				{
					Max = Min;
					Min = dist[viz] + p;
					continue;
				}
				if(dist[viz] + p < Max)	Max = dist[viz] + p;
			}
			dist[x] = Max;
		}
	}
	debug("terminei a entrada\n");
	dijkstra();
	debug("foi o dijkstra\n");
	int resp = dist[0];
	debug("resp = %d\n",resp);
	return resp;
}

Compilation message (stderr)

crocodile.cpp: In function 'void dijkstra()':
crocodile.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int x = 0; x < grafo[cur].size(); x++)
                  ~~^~~~~~~~~~~~~~~~~~~
crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:83:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int y = 0; y < grafo[x].size(); y++)
                   ~~^~~~~~~~~~~~~~~~~

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