Submission #5039

#	Time	Username	Problem	Language	Result	Execution time	Memory
5039		cki86201	Crocodile's Underground City (IOI11_crocodile)	C++98	46 / 100	640 ms	146280 KiB

crocodile

#include "crocodile.h"
#include <queue>
using namespace std;

typedef pair<int,int> Pi;
#define X first
#define Y second

int st[100010], en[2000020], nxt[2000020], len[2000020];
void add(int s,int e,int l,int c){nxt[c]=st[s],st[s]=c,len[c]=l,en[c]=e;}

priority_queue <Pi, vector<Pi>, greater<Pi> > pq;
int p[100010][2];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	int i;
	for(i=0;i<N;i++)st[i] = -1;
	for(i=0;i<M;i++)add(R[i][0],R[i][1],L[i],i<<1), add(R[i][1],R[i][0],L[i],i<<1|1);
	for(i=0;i<K;i++)pq.push(Pi(0,P[i]));
	while(!pq.empty()){
		Pi tmp = pq.top();
		pq.pop();
		if(tmp.X > p[tmp.Y][1])continue;
		for(i=st[tmp.Y];i!=-1;i=nxt[i]){
			int &a = p[en[i]][0], &b = p[en[i]][1], l = tmp.X + len[i];
			if(!a||a>l){
				b=a, a=l;
				if(b)pq.push(Pi(b, en[i]));
			}
			else if(!b||b>l)b=l, pq.push(Pi(b, en[i]));
		}
	}
	return p[0][1];
}

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