oj.uz

Submission #13199

# Submission time Handle Problem Language Result Execution time Memory
13199 2015-02-02T14:09:53 Z pseudopodia Crocodile's Underground City (IOI11_crocodile) C++
100 / 100
 699 ms 159396 KB 
#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.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 124536 KB Output is correct
2 Correct 0 ms 124536 KB Output is correct
3 Correct 0 ms 124536 KB Output is correct
4 Correct 0 ms 124536 KB Output is correct
5 Correct 0 ms 124536 KB Output is correct
6 Correct 0 ms 124536 KB Output is correct
7 Correct 3 ms 124536 KB Output is correct
8 Correct 0 ms 124536 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 124668 KB Output is correct
2 Correct 0 ms 124536 KB Output is correct
3 Correct 4 ms 124536 KB Output is correct
4 Correct 8 ms 124668 KB Output is correct
5 Correct 6 ms 124800 KB Output is correct
6 Correct 0 ms 124536 KB Output is correct
7 Correct 0 ms 124536 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 152528 KB Output is correct
2 Correct 139 ms 132328 KB Output is correct
3 Correct 144 ms 132976 KB Output is correct
4 Correct 699 ms 159396 KB Output is correct
5 Correct 349 ms 147356 KB Output is correct
6 Correct 54 ms 127696 KB Output is correct
7 Correct 383 ms 143772 KB Output is correct