Submission #130918

#	Time	Username	Problem	Language	Result	Execution time	Memory
130918		Mahdi_Jfri	Rail (IOI14_rail)	C++14	56 / 100	707 ms	99088 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 5e3 + 20;

int d[maxn][maxn];

void findLocation(int N, int first, int location[], int stype[])
{
	int n = N;
	for(int i = 0; i < n; i++)
		for(int j = i + 1; j < n; j++)
			d[i][j] = d[j][i] = getDistance(i , j);

	vector<pair<int , int> > tmp;
	for(int i = 1; i < n; i++)
		tmp.pb({d[0][i] , i});
	sort(tmp.begin() , tmp.end());

	vector<int> rd;
	for(auto x : tmp)
	{
		int v = x.second;
		bool bad = 0;
		if(!rd.empty())
		{
			int lx = d[0][rd.back()] - d[rd.back()][v];
			int tmp = -1;
			for(auto u : rd)
				if(d[0][u] >= lx)
				{
					tmp = u;
					break;
				}

			if(d[0][v] == d[v][tmp] + d[tmp][0])
				bad = 1;
		}

		if(!bad)
			rd.pb(v) , stype[v] = 2;
	}

	tmp.clear();
	while(rd.empty());
	int r = rd.back();
	for(int i = 0; i < n; i++)
		if(i != r)
			tmp.pb({d[r][i] , i});
	sort(tmp.begin() , tmp.end());

	vector<int> c;

	for(auto x : tmp)
	{
		int v = x.second;
		bool bad = 0;
		for(auto u : c)
			if(d[r][v] == d[r][u] + d[u][v])
				bad = 1;

		if(!bad)
			c.pb(v) , stype[v] = 1;
	}

	for(int i = 0; i < n; i++)
		if(!stype[i])
			stype[i] = 2;

	location[r] = first + d[0][r];
	for(int i = 0; i < n; i++)
		if(stype[i] == 1)
			location[i] = location[r] - d[r][i];

	for(int i = 0; i < n; i++)
		if(stype[i] == 2)
			location[i] = location[c.back()] + d[c.back()][i];

}

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