Submission #705945

#	Time	Username	Problem	Language	Result	Execution time	Memory
705945		SamNguyen	Rail (IOI14_rail)	C++14	56 / 100	476 ms	98508 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

const int TYPE_C = 1, TYPE_D = 2;
const int INF = 1e9;
const int MAX = 5000;

template <class T1, class T2>
inline bool minimise(T1 &x, T2 y) {
	if (x > y) { x = y; return true; }
	return false;
}

int N, dist[MAX][MAX];

int getMinIndex(int x) {
	int cur_d = INF, y = -1;
	for (int i = 0; i < N; i++) if (i != x)
		if (minimise(cur_d, dist[x][i]))
			y = i;
	return y;
}

void findLocation(int _N, int s0, int s[], int t[]) {
	N = _N;
	s[0] = s0;
	t[0] = TYPE_C;

	for (int i = 0; i < N; i++)	{
		dist[i][i] = 0;
		for (int j = i + 1; j < N; j++)
			dist[i][j] = dist[j][i] = getDistance(i, j);
	}

	int y = getMinIndex(0);	
	int x = getMinIndex(y);	

	s[y] = s[0] + dist[0][y];
	t[y] = TYPE_D;

	s[x] = s[y] - dist[x][y];
	t[x] = TYPE_C;

	vector<int> lefts = (x == 0 ? vector<int>{0} : vector<int>{0, x}), rights = {y};

	for (int i = 1; i < N; i++) if (i != x and i != y) {
		if (dist[x][i] > dist[y][i]) 
			lefts.push_back(i);	
		else
			rights.push_back(i);
	}

	for (int i : lefts) {
		t[i] = TYPE_C;
		s[i] = s[y] - dist[y][i];
	}

	for (int i : rights) {
		t[i] = TYPE_D;
		s[i] = s[x] + dist[x][i];
	}

	for (int i : rights) for (int j : rights) if (i != j) {
		if (dist[i][x] - dist[j][x] == dist[i][j]) {
			t[i] = TYPE_C;
			t[j] = TYPE_D;

			s[j] = s[x] + dist[j][x];
			s[i] = s[j] - dist[j][i];
		}
	}

	for (int i : lefts) for (int j : lefts) if (i != j) {
		if (dist[i][y] - dist[j][y] == dist[i][j]) {
			t[i] = TYPE_D;
			t[j] = TYPE_C;

			s[j] = s[y] - dist[j][y];
			s[i] = s[j] + dist[j][i];
		}
	}
}

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