Submission #598876

#	Time	Username	Problem	Language	Result	Execution time	Memory
598876		BT21tata	Rail (IOI14_rail)	C++17	30 / 100	426 ms	98404 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

int dis[5005][5005], opt[5005];

void findLocation(int n, int first, int location[], int stype[])
{
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<n; j++)
		{
			if(i<j) dis[i][j]=getDistance(i, j);
			else dis[i][j]=dis[j][i];
		}
	}
	opt[0]=1;
	location[0]=first;
	stype[0]=1;
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<n; j++)
		{
			if(i!=j and dis[i][j]<dis[i][opt[i]])
				opt[i]=j;
		}
	}
	stype[opt[0]]=2;
	location[opt[0]]=first+dis[0][opt[0]];
	for(int i=1; i<n; i++)
	{
		if(i==opt[0]) continue;
		if(opt[i]==0)
		{
			stype[i]=2;
			location[i]=first+dis[0][i];
		}
		else if(opt[i]==opt[0])
		{
			stype[i]=1;
			location[i]=location[opt[0]]-dis[opt[0]][i];
		}
		else if(dis[0][i]<dis[opt[0]][i])
		{
			if(dis[0][i]<dis[0][opt[i]])
			{
				stype[i]=2;
				location[i]=first+dis[0][i];
			}
			else
			{
				stype[i]=1;
				location[i]=first+dis[0][opt[i]]-dis[i][opt[i]];
			}
		}
		else
		{
			if(dis[opt[0]][i]<dis[opt[0]][opt[i]])
			{
				stype[i]=1;
				location[i]=location[opt[0]]-dis[opt[0]][i];
			}
			else
			{
				stype[i]=2;
				location[i]=location[opt[0]]-dis[opt[0]][opt[i]]+dis[opt[i]][i];
			}
		}
	}
}

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44