Submission #13199

#	Time	Username	Problem	Language	Result	Execution time	Memory
13199		pseudopodia	Crocodile's Underground City (IOI11_crocodile)	C++98	100 / 100	699 ms	159396 KiB

crocodile

#include "crocodile.h"
#include <vector>
#include <queue>
#define maxV 100010
#define INF 1000000010
using namespace std;

struct Data{
	int val, x;
	Data(){}
	Data(int x, int val){ this->x = x, this->val = val; }
	inline bool operator < (const Data &c) const{
		return val > c.val;
	}
} top;

struct Node{
	int val1, val2;
	void init(){ val1=val2=INF; }
	bool update(int val)
	{
		if( val1 > val )
		{
			val2 = val1, val1 = val;
			return true;
		}
		else if( val2 > val )
		{
			val2 = val;
			return true;
		}
		return false;
	}
}info[maxV];

priority_queue<Data> pq;
vector<int> map[maxV], dist[maxV];
bool visit[maxV];

int travel_plan(int v, int e, int edge[][2], int len[], int exitN, int exit[])
{
	for(int i=0;i<v;i++)
	{
		map[i].clear(), dist[i].clear();
		info[i].init(), visit[i] = false;
	}

	for(int i=0;i<e;i++)
	{
		map[edge[i][0]].push_back(edge[i][1]);
		map[edge[i][1]].push_back(edge[i][0]);
		dist[edge[i][0]].push_back(len[i]);
		dist[edge[i][1]].push_back(len[i]);
	}
	
	while( !pq.empty() ) pq.pop();
	for(int i=0;i<exitN;i++) pq.push(Data(exit[i],0));

	int x, y, z;
	while( !pq.empty() )
	{
		do{
			top = pq.top(), x = top.x;
			pq.pop();
		}while( visit[top.x] );

		if( x == 0 ) return top.val;
		
		visit[x] = true;
		for(int j=0;j<map[x].size();j++)
		{
			y = map[x][j], z = dist[top.x][j];
			if( !visit[y] && info[y].update(top.val+z) ) pq.push(Data(y,info[y].val2));
		}
	}

	return -1;
}

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