Submission #130923

#	Time	Username	Problem	Language	Result	Execution time	Memory
130923		Mahdi_Jfri	Rail (IOI14_rail)	C++14	30 / 100	123 ms	43136 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];

int get(int i , int j)
{
	if(i != j && !d[i][j])
		d[i][j] = d[j][i] = getDistance(i , j);

	return d[i][j];
}

void findLocation(int N, int first, int location[], int stype[])
{
	int n = N;

	vector<pair<int , int> > tmp;
	for(int i = 1; i < n; i++)
		tmp.pb({get(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 = get(0 , rd.back()) - get(rd.back() , v);
			int tmp = -1;
			for(auto u : rd)
				if(get(0 , u) >= lx)
				{
					tmp = u;
					break;
				}

			if(get(0 , v) == get(v , tmp) + get(tmp , 0))
				bad = 1;
		}

		if(!bad)
			location[v] = get(0 , v) , rd.pb(v) , stype[v] = 2;
		else
			stype[v] = 1 , location[v] = get(0 , rd.back()) - get(rd.back() , v);
	}

	for(int i = 0; i < n; i++)
		location[i] += first;
	stype[0] = 1;
}

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