Submission #596958

#	Time	Username	Problem	Language	Result	Execution time	Memory
596958		Elias	Rail (IOI14_rail)	C++17	56 / 100	445 ms	99076 KiB

rail

#include <bits/stdc++.h>

using namespace std;

#include "rail.h"

#define all(x) x.begin(), x.end()

int n;

vector<bool> found;

vector<vector<int>> d;

int getDistance(int i, int j);

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

	d = vector<vector<int>>(n, vector<int>(n, 1e9));

	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
			d[i][j] = d[j][i] = getDistance(i, j);

	int b = min_element(all(d[0])) - d[0].begin();
	location[b] = first + d[0][b];
	stype[b] = 2;

	int a = min_element(all(d[b])) - d[b].begin();
	location[a] = location[b] - d[b][a];
	stype[a] = 1;

	set<int> left, right;

	for (int i = 0; i < n; i++)
	{
		if (i == a || i == b)
			continue;

		if (d[a][i] < d[b][i])
			right.insert(i);
		else
			left.insert(i);
	}

	auto solveSide = [&](set<int> group, int flip, int a, int b)
	{
		while (group.size())
		{
			int c = -1;
			int dist = 1e9;

			for (int x : group)
				if (d[a][x] < dist)
					dist = d[a][x], c = x;

			location[c] = location[a] + (flip ? -dist : dist);
			stype[c] = 2 - flip;

			int D = -1;
			for (int x : group)
				if (d[c][x] < dist)
					dist = d[c][x], D = x;

			if (D != -1)
			{
				location[D] = location[c] - (flip ? -dist : dist);
				stype[D] = 1 + flip;

				vector<int> toRemove;

				for (int x : group)
					if (d[c][x] < d[D][x])
					{
						location[x] = location[c] - (flip ? -d[c][x] : d[c][x]);
						stype[x] = 1 + flip;
						toRemove.push_back(x);
					}

				for (int x : toRemove)
					group.erase(x);

				a = D;
				b = c;
			}

			group.erase(c);
			group.erase(D);
		}
	};

	solveSide(right, 0, a, b);
	solveSide(left, 1, b, a);
}

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