Submission #133546

#	Time	Username	Problem	Language	Result	Execution time	Memory
133546		tinjyu	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	3 ms	504 KiB

crocodile

#include "crocodile.h"
#include <iostream>
using namespace std;
bool fin[100005];
int t[25000005],c[100005],road[5000005][3],map[100005];
long long mi[100005][4];
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
	for(register int i=0;i<n;i++)
	{
		map[i]=-1;
		mi[i][0]=9999999999;
		mi[i][1]=9999999999;
		mi[i][2]=-1;
		mi[i][3]=-1;
	}
	for(register int i=0;i<m;i++)
	{
		road[i*2][0]=r[i][0];
		road[i*2][1]=map[r[i][1]];
		road[i*2][2]=road[i*2+1][2]=l[i];
		map[r[i][1]]=i*2;
		road[i*2+1][0]=r[i][1];
		road[i*2+1][1]=map[r[i][0]];
		map[r[i][0]]=i*2+1;
	}

	register int pp=0,qq=k-1;
	for(register int i=0;i<k;i++)
	{
		t[i]=p[i];
		c[p[i]]=2;
		mi[p[i]][0]=0;
		mi[p[i]][1]=0;
	}
	while(pp<=qq)
	{
		if(c[t[pp]]>=2&& fin[t[pp]]==0)
		{
			int q=map[t[pp]];
			while(q!=-1)
			{
				if(fin[road[q][0]]==0)
				{
					qq++;
					c[road[q][0]]++;
					t[qq]=road[q][0];
				}
				q=road[q][1];
			}
			fin[t[pp]]=1;
		}
		pp++;
	}
	pp=0;
	qq=k-1;
	for(register int i=0;i<n;i++)fin[i]=0;
	while(pp<=qq)
	{
		while((fin[t[pp]]==1 || mi[t[pp]][1]==9999999999) && pp<=qq)pp++;
		if(pp>qq)break;
		int x=t[pp];
		int q=map[x];
		while(q!=-1)
		{
			int now=road[q][0];
			if(c[now]>=2)
			{
				qq++;
				t[qq]=now;
				if(mi[x][1]+road[q][2]<mi[now][1] && mi[x][1]+road[q][2]>mi[now][0])
				{
					fin[now]=0;
					mi[now][1]=mi[x][1]+road[q][2];
					mi[now][3]=x;
				}
				else if(mi[x][1]+road[q][2]<mi[now][0])
				{
					if(x==mi[now][2])mi[now][0]=mi[x][1]+road[q][2];
					else
					{
						fin[now]=0;
						mi[now][1]=mi[now][0];
						mi[now][3]=mi[now][2];
						mi[now][0]=mi[x][1]+road[q][2];
						mi[now][2]=x;
					}
				}	
				
			}
			q=road[q][1];
		}
 
 
		fin[t[pp]]=1;
		pp++;
	}
  	return mi[0][1];
}

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