Submission #130929

#	Time	Username	Problem	Language	Result	Execution time	Memory
130929		Mahdi_Jfri	Rail (IOI14_rail)	C++14	56 / 100	167 ms	68244 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 , shit;
	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
		{
			if(get(0 , rd.back()) - get(rd.back() , v) > 0)
				stype[v] = 1 , location[v] = get(0 , rd.back()) - get(rd.back() , v);
			else
			{
				d[rd[0]][v] = d[v][rd[0]] = d[0][v] - d[0][rd[0]];
				shit.pb(v);
			}
		}
	}

	int r = rd[0];
	rd.clear() , tmp.clear();
	rd.pb(0);
	for(auto v : shit)
	{
		bool bad = 0;
		if(!rd.empty())
		{
			int lx = get(r , rd.back()) - get(rd.back() , v);
			int tmp = -1;
			for(auto u : rd)
				if(get(r , u) >= lx)
				{
					tmp = u;
					break;
				}

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

		if(!bad)
			location[v] = location[r] - get(r , v) , rd.pb(v) , stype[v] = 1;
		else
		{
			if(get(r , rd.back()) - get(rd.back() , v) > 0)
				stype[v] = 2 , location[v] = location[r] - (get(r , rd.back()) - get(rd.back() , v));
			else
			{
				cout << "HERE" << endl;
				assert(0);
			}
		}
	}

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

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