Submission #133541

#	Time	Username	Problem	Language	Result	Execution time	Memory
133541		tinjyu	Crocodile's Underground City (IOI11_crocodile)	C++14	89 / 100	2051 ms	156280 KiB

crocodile

#include "crocodile.h"
#include <iostream>
using namespace std;
long long int fin[100005],t[25000005],c[100005],road[5000005][3],map[100005],mi[100005][4],tag[100005];
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;
	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]=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]];
		road[i*2+1][2]=l[i];
		map[r[i][0]]=i*2+1;
	}
	for(register int i=0;i<n;i++)
	{
		mi[i][0]=9999999999;
		mi[i][1]=9999999999;
		mi[i][2]=-1;
		mi[i][3]=-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++;
	}
	for(register int i=0;i<k;i++)t[i]=p[i];
	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 q=map[t[pp]];
		while(q!=-1)
		{
			if(c[road[q][0]]>=2)
			{
				qq++;
				t[qq]=road[q][0];
				if(mi[t[pp]][1]+road[q][2]<mi[road[q][0]][0])
				{
					
					if(t[pp]==mi[road[q][0]][2])mi[road[q][0]][0]=mi[t[pp]][1]+road[q][2];
					else
					{
						fin[road[q][0]]=0;
						mi[road[q][0]][1]=mi[road[q][0]][0];
						mi[road[q][0]][3]=mi[road[q][0]][2];
						mi[road[q][0]][0]=mi[t[pp]][1]+road[q][2];
						mi[road[q][0]][2]=t[pp];
					}
				}	
				else if(mi[t[pp]][1]+road[q][2]<mi[road[q][0]][1])
				{
					fin[road[q][0]]=0;
					mi[road[q][0]][1]=mi[t[pp]][1]+road[q][2];
					mi[road[q][0]][3]=t[pp];
				}
			}
			q=road[q][1];
		}
 
 
		fin[t[pp]]=1;
		pp++;
	}
  return mi[0][1];
}

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