Submission #168335

#	Time	Username	Problem	Language	Result	Execution time	Memory
168335		johutha	Rail (IOI14_rail)	C++14	56 / 100	457 ms	760 KiB

rail

#include "rail.h"
#include <queue>
#include <vector>
#include <iostream>
#include <set>

using namespace std;

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

	vector<int> mindist(N, (int)1e9);
	vector<int> minsource(N, -1);

	for (int i = 1; i < N; i++)
	{
		int qdist = getDistance(0, i);
		if (qdist <= mindist[i])
		{
			mindist[i] = qdist;
			minsource[i] = 0;
		}
	}

	mindist[0] = -1;

	for (int k = 1; k < N; k++)
	{
		int curr = -1;
		int cdist = 1e8;
		for (int i = 1; i < N; i++)
		{
			if (mindist[i] < cdist && mindist[i] != -1)
			{
				cdist = mindist[i];
				curr = i;
			}
		}

		int src = minsource[curr];
		int pos = location[src] + mindist[curr]*(stype[src] == 1 ? 1 : -1);
		location[curr] = pos;
		stype[curr] = (stype[src] == 1 ? 2 : 1);
		mindist[curr] = -1;

		for (int i = 1; i < N; i++)
		{
			if (mindist[i] == -1) continue;
			int qdist = getDistance(curr, i);
			if (qdist <= mindist[i])
			{
				mindist[i] = qdist;
				minsource[i] = curr;
			}
		}
	}
}

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