Submission #5040

#	Time	Username	Problem	Language	Result	Execution time	Memory
5040		cki86201	Crocodile's Underground City (IOI11_crocodile)	C++98	100 / 100	652 ms	146376 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];
bool chk[100010];

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(chk[tmp.Y])continue;
		chk[tmp.Y] = 1;
		for(i=st[tmp.Y];i!=-1;i=nxt[i]){
			if(chk[en[i]])continue;
			int &a = p[en[i]][0], &b = p[en[i]][1], l = tmp.X + len[i], s = b;
			if(!a||a>l)b=a, a=l;
			else if(!b||b>l)b=l;
			if(b!=s)pq.push(Pi(b,en[i]));
		}
	}
	return p[0][1];
}

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