Submission #133642

#	Time	Username	Problem	Language	Result	Execution time	Memory
133642		zozder	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	154 ms	189048 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];
long long way[maxn];
long long sort[maxm][2];
long long ans=-1;
long long d[maxn];

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

void dfs(long long x, long long value)
{
	int p=x;
	if(way[x]==1)
	{
//		cout<<value<<endl;
		if(ans==-1||value<ans)ans=value;
	}
	else
	{
		while(a[p][0]!=-1)
		{
			p=a[p][0];
			if(a[p][0]!=-1)
			{
				if(d[a[p][1]]==-1||value+a[p][2]<=d[a[p][1]])
				{
					d[a[p][1]]=value+a[p][2];
					dfs(a[p][1],value+a[p][2]);
				}
			}
		}
	}
}

int travel_plan(int n, int m, int R[][2], int L[], int K, int P[])
{
	for(long long i=0;i<4*maxm;i++)
	{
		map[i][0]=-1;
		a[i][0]=-1;
	}
	for(long long i=0;i<maxn;i++)d[i]=-1;
	for(long long i=0;i<n;i++)way[i]=0;
	for(long long i=0;i<K;i++)way[P[i]]=1;
	
	o=n-1;
	for(long long 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(long long i=0;i<=o;i++)cout<<i<<"\t";cout<<endl;
	for(long long i=0;i<=o;i++)cout<<map[i][0]<<"\t";cout<<endl;
	for(long long i=0;i<=o;i++)cout<<map[i][1]<<"\t";cout<<endl;
	for(long long i=0;i<=o;i++)cout<<map[i][2]<<"\t";cout<<endl;
	cout<<"---------------------"<<endl;*/
	o=n-1;
	for(long long i=0;i<n;i++)
	{
		long long 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(long long j=1;j<=oo;j++)cout<<j<<"\t";cout<<endl;
		for(long long j=1;j<=oo;j++)cout<<sort[j][0]<<"\t";cout<<endl;
		for(long long j=1;j<=oo;j++)cout<<sort[j][1]<<"\t";cout<<endl;
		cout<<"------------------------"<<endl;*/
		for(long long 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(long long i=0;i<=o;i++)cout<<i<<"\t";cout<<endl;
	for(long long i=0;i<=o;i++)cout<<a[i][0]<<"\t";cout<<endl;
	for(long long i=0;i<=o;i++)cout<<a[i][1]<<"\t";cout<<endl;
	for(long long i=0;i<=o;i++)cout<<a[i][2]<<"\t";cout<<endl;
	cout<<"---------------------"<<endl;*/
	d[0]=0;
	dfs(0,0);
//	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