Submission #399954

#	Time	Username	Problem	Language	Result	Execution time	Memory
399954		Kenzo_1114	Rail (IOI14_rail)	C++17	30 / 100	146 ms	98500 KiB

rail

#include<bits/stdc++.h>
#include "rail.h"
using namespace std;
const int MAXN = 5010;

int dist[MAXN][MAXN];
vector<pair<int, int> > leftBlocks, rightBlocks;

void get(int i, int j)
{
	if(dist[i][j] != -1)	return;
	dist[i][j] = dist[j][i] = getDistance(i, j);
}

void findLocation(int n, int first, int location[], int stype[])
{
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			dist[i][j] = (i == j) ? 0 : -1;

	int L = 0, R = 0;
	for(int i = 1; i < n; i++)	
	{
		get(0, i);
		if(!R || dist[0][i] < dist[0][R])	R = i;
	}

	location[0] = first;
	location[R] = first + dist[0][R];
	stype[0] = 1;
	stype[R] = 2;

	for(int i = 1; i < n; i++)	
	{
		if(i == R)	continue;
		get(R, i);
		if(dist[R][i] < dist[R][L])	L = i;
	}

	location[L] = location[R] - dist[R][L];
	stype[L] = 1;

	for(int i = 1; i < n; i++)
		dist[L][i] = dist[0][i] - (dist[0][R] - dist[L][R]);

	for(int i = 0; i < n; i++)
	{
		if(i == L || i == R)	continue;

		if(dist[L][i] < dist[R][i])
			rightBlocks.push_back({dist[L][i], i});
		else
			leftBlocks.push_back({dist[R][i], i});
	}

	sort(leftBlocks.begin(), leftBlocks.end());
	sort(rightBlocks.begin(), rightBlocks.end());

	int R2 = R;
	for(int i = 0; i < (int) rightBlocks.size(); i++)
	{
		int id = rightBlocks[i].second;
		int d = rightBlocks[i].first;
		get(R, id);

		if(d - dist[L][R] == dist[id][R])	
		{
			location[id] = location[R] - dist[id][R];
			stype[id] = 1;
		}
		else
		{
			location[id] = location[L] + d;
			stype[id] = 2;
			R = id;
		}
	}

	R = R2;
	for(int i = 0; i < (int) leftBlocks.size(); i++)
	{
		int id = leftBlocks[i].second;
		int d = leftBlocks[i].first;
		get(L, id);

		if(d - dist[L][R] == dist[L][id])	
		{
			location[id] = location[L] + dist[id][L];
			stype[id] = 2;
		}
		else
		{
			location[id] = location[R] - d;
			stype[id] = 1;
			L = id;
		}
	}
}

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