Submission #763379

#	Time	Username	Problem	Language	Result	Execution time	Memory
763379		SanguineChameleon	Rail (IOI14_rail)	C++17	100 / 100	91 ms	102708 KiB

rail

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

const int maxN = 5e3 + 20;
const int maxM = 1e6 + 20;
int *location;
int *stype;
int btype[maxM];
int memo[maxN][maxN];
int X, Y, L, R;

int dist(int u, int v) {
	if (memo[u][v] != -1) {
		return memo[u][v];
	}
	else {
		return memo[u][v] = memo[v][u] = getDistance(u, v);
	}
}

bool cmpX(int u, int v) {
	return dist(X, u) < dist(X, v);
}

bool cmpY(int u, int v) {
	return dist(Y, u) < dist(Y, v);
}

void answer(int id, int loc, int type) {
	location[id] = loc;
	stype[id] = type;
	btype[loc] = type;
}

void findLocation(int N, int first, int _location[], int _stype[]) {
	location = _location;
	stype = _stype;
	for (int i = 0; i < N; i++) {
		location[i] = -1;
		stype[i] = -1;
		for (int j = 0; j < N; j++) {
			memo[i][j] = -1;
		}
	}
	for (int i = 0; i < maxM; i++) {
		btype[i] = -1;
	}
	X = 0;
	answer(X, first, 1);
	Y = 1;
	for (int i = 0; i < N; i++) {
		if (i != X && dist(X, i) < dist(X, Y)) {
			Y = i;
		}
	}
	answer(Y, location[X] + dist(X, Y), 2);
	vector<int> left;
	vector<int> right;
	for (int i = 0; i < N; i++) {
		if (i == X || i == Y) {
			continue;
		}
		if (dist(X, i) == dist(X, Y) + dist(Y, i)) {
			if (dist(Y, i) < dist(Y, X)) {
				answer(i, location[Y] - dist(Y, i), 1);
			}
			else {
				left.push_back(i);
			}
		}
		else {
			right.push_back(i);
		}
	}
	sort(left.begin(), left.end(), cmpX);
	sort(right.begin(), right.end(), cmpY);
	L = X;
	R = Y;
	for (auto i: left) {
		int B = (dist(L, i) - dist(R, i) + location[L] + location[R]) / 2;
		if (btype[B] == 1) {
			int A = location[L] + dist(L, i);
			answer(i, A, 2);
		}
		else {
			int A = location[R] - dist(R, i);
			answer(i, A, 1);
			L = i;
		}
	}
	L = X;
	R = Y;
	for (auto i: right) {
		int B = (dist(L, i) - dist(R, i) + location[L] + location[R]) / 2;
		if (btype[B] == 2) {
			int A = location[R] - dist(R, i);
			answer(i, A, 1);
		}
		else {
			int A = location[L] + dist(L, i);
			answer(i, A, 2);
			R = i;
		}
	}
}

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