Submission #599047

#	Time	Username	Problem	Language	Result	Execution time	Memory
599047		BT21tata	Rail (IOI14_rail)	C++17	56 / 100	934 ms	196732 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
typedef long long ll;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define F first
#define S second
using namespace std;

ll 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];
		}
	}

	vector<pii>d0;
	for(int i=1; i<n; i++)
	{
		d0.pb({dis[0][i], i});
	}
	sort(all(d0));
	int l=0, r=d0[0].S;
	stype[0]=1;
	location[0]=first;
	stype[d0[0].S]=2;
	location[d0[0].S]=first+d0[0].F;
	for(int i=1; i<n-1; i++)
	{
		int k=d0[i].S;
		bool f=0;
		if(dis[l][k]>dis[r][k]) f=1;
		for(int e=0; e<n; e++)
		{
			if(e!=l and e!=k and dis[l][e]+dis[e][k]==dis[l][k])
			{
				f=1;
				break;
			}
		}
		for(int e=0; e<n; e++)
		{
			if(e!=r and e!=k and dis[r][e]+dis[e][k]==dis[r][k])
			{
				f=0;
				break;
			}
		}
		if(f)
		{
			stype[k]=1;
			location[k]=location[r]-dis[r][k];
			if(location[k]<location[l]) l=k;
		}
		else
		{
			stype[k]=2;
			location[k]=location[l]+dis[l][k];
			if(location[k]>location[r]) r=k;
		}
	}
}

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