Submission #133547

#	Time	Username	Problem	Language	Result	Execution time	Memory
133547		zozder	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	272 ms	251640 KiB

crocodile

#include "crocodile.h"
#include <iostream>
#include <cstdlib>
#define maxn 100005
#define maxm 1000005
using namespace std;
long long map[4*maxm][3],o;
long long a[4*maxm][3];
int way[maxn];
long long sort[maxm][2];
long long heap[4*maxm][2],ho=0;
long long d[maxn];

void down(int point, long long value, int x)
{
	ho++;
	x++;
	heap[x][0]=point;
	heap[x][1]=value;
	while(heap[x][1]<heap[x/2][1]&&x>1)
	{
		swap(heap[x][0],heap[x/2][0]);
		swap(heap[x][1],heap[x/2][1]);
		x=x/2;
	}
}

void push(int point)
{
	int p=point;
	while(a[a[p][0]][0]!=-1)
	{
		p=a[p][0];
		down(a[p][1],d[point]+a[p][2],ho);
	}
}

void pop()
{
	long long temp=heap[1][0],t=0;
	if(d[heap[1][0]]==-1)
	{
		t=1;
		d[heap[1][0]]=heap[1][1];
	}
	else d[heap[1][0]]=min(d[heap[1][0]],heap[1][1]);
	swap(heap[1][0],heap[ho][0]);
	swap(heap[1][1],heap[ho][1]);
	ho--;
	long long x=1;
	if(ho>0)
	{
		while((heap[x][1]>heap[2*x][1]||heap[x][1]>heap[2*x+1][1])&&(2*x<=ho||2*x+1<=ho))
		{
			if(heap[x][1]>heap[2*x][1]&&heap[x][1]>heap[2*x+1][1])
			{
				if(heap[2*x][1]>heap[2*x+1][1]&&2*x<=ho)
				{
					swap(heap[x][0],heap[2*x][0]);
					swap(heap[x][1],heap[2*x][1]);
					x=2*x;
				}
				else if(2*x+1<=ho)
				{
					swap(heap[x][0],heap[2*x+1][0]);
					swap(heap[x][1],heap[2*x+1][1]);
					x=2*x+1;
				}
			}
			else if(heap[x][1]>heap[2*x][1]&&2*x<=ho)
			{
				swap(heap[x][0],heap[2*x][0]);
				swap(heap[x][1],heap[2*x][1]);
				x=2*x;
			}
			else if(2*x+1<=ho)
			{
				swap(heap[x][0],heap[2*x+1][0]);
				swap(heap[x][1],heap[2*x+1][1]);
				x=2*x+1;
			}
		}
	}
	if(t==1&&way[temp]==0)push(temp);
}

int compare(const void *x, const void *y)
{
	return ((int*)x)[1] - ((int*)y)[1];
}

int travel_plan(int n, int m, int R[][2], int L[], int K, int P[])
{
	for(int i=0;i<4*maxm;i++)
	{
		map[i][0]=-1;
		a[i][0]=-1;
		heap[i][0]=-1;
		heap[i][1]=-1;
	}
	for(int i=0;i<maxn;i++)d[i]=-1;
	for(int i=0;i<n;i++)way[i]=0;
	for(int i=0;i<K;i++)way[P[i]]=1;
	
	o=n-1;
	for(int i=0;i<m;i++)
	{
		o++;
		map[o][1]=R[i][1];
		map[o][2]=L[i];
		map[o][0]=map[R[i][0]][0];
		map[R[i][0]][0]=o;
		o++;
		map[o][1]=R[i][0];
		map[o][2]=L[i];
		map[o][0]=map[R[i][1]][0];
		map[R[i][1]][0]=o;
	}
/*	for(int i=0;i<=o;i++)cout<<i<<"\t";cout<<endl;
	for(int i=0;i<=o;i++)cout<<map[i][0]<<"\t";cout<<endl;
	for(int i=0;i<=o;i++)cout<<map[i][1]<<"\t";cout<<endl;
	for(int i=0;i<=o;i++)cout<<map[i][2]<<"\t";cout<<endl;
	cout<<"---------------------"<<endl;*/
	o=n-1;
	for(int i=0;i<n;i++)
	{
		int p=i,lo=1,oo=0;
		while(map[p][0]!=-1)
		{
			p=map[p][0];
			oo++;
			sort[oo][0]=map[p][1];
			sort[oo][1]=map[p][2];
			if(way[map[p][1]]==1)
			{
				swap(sort[oo][0],sort[lo][0]);
				swap(sort[oo][1],sort[lo][1]);
				lo++;
			}
		}
		qsort(sort+lo,oo-lo+1,sizeof(long long)*2,compare);
		if(lo>1)qsort(sort+1,lo-1,sizeof(long long)*2,compare);
/*		cout<<i<<","<<lo<<","<<oo<<":"<<endl;
		for(int j=1;j<=oo;j++)cout<<j<<"\t";cout<<endl;
		for(int j=1;j<=oo;j++)cout<<sort[j][0]<<"\t";cout<<endl;
		for(int j=1;j<=oo;j++)cout<<sort[j][1]<<"\t";cout<<endl;
		cout<<"------------------------"<<endl;*/
		for(int j=1;j<=oo;j++)
		{
			o++;
			a[o][1]=sort[j][0];
			a[o][2]=sort[j][1];
			a[o][0]=a[i][0];
			a[i][0]=o;
		}
	}
/*	for(int i=0;i<=o;i++)cout<<i<<"\t";cout<<endl;
	for(int i=0;i<=o;i++)cout<<a[i][0]<<"\t";cout<<endl;
	for(int i=0;i<=o;i++)cout<<a[i][1]<<"\t";cout<<endl;
	for(int i=0;i<=o;i++)cout<<a[i][2]<<"\t";cout<<endl;
	cout<<"---------------------"<<endl;*/
	d[0]=0;
	push(0);
	while(ho>0)
	{
/*		for(int i=1;i<=ho;i++)cout<<i<<"\t";cout<<endl;
		for(int i=1;i<=ho;i++)cout<<heap[i][0]<<"\t";cout<<endl;
		for(int i=1;i<=ho;i++)cout<<heap[i][1]<<"\t";cout<<endl;*/
		pop();
/*		for(int i=1;i<=ho;i++)cout<<i<<"\t";cout<<endl;
		for(int i=1;i<=ho;i++)cout<<heap[i][0]<<"\t";cout<<endl;
		for(int i=1;i<=ho;i++)cout<<heap[i][1]<<"\t";cout<<endl;*/
	}
	long long ans=-1;
	for(int i=0;i<K;i++)if((d[P[i]]<ans||ans==-1)&&d[P[i]]!=-1)ans=d[P[i]];
//	for(int i=0;i<n;i++)cout<<d[i]<<"\t";cout<<endl;
	return ans;
}

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