제출 #704620

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
704620		SamNguyen	철로 (IOI14_rail)	C++14	30 / 100	261 ms	98260 KiB

rail

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

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

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_C = {0, x}, rights_D = {y}, unknowns;

	for (int i = 1; i < N; i++) if (i != x and i != y) {
		if (dist[x][i] == dist[x][y] + dist[y][i]) {
			s[i] = s[y] - dist[y][i];
			t[i] = TYPE_C;
			lefts_C.push_back(i);
		}
		else if (dist[y][i] == dist[x][y] + dist[x][i]) {
			s[i] = s[x] + dist[x][i];
			t[i] = TYPE_D;
			rights_D.push_back(i);
		}
		else
			unknowns.push_back(i);	
	}

	for (int i : unknowns) [&]() {
		for (int z : lefts_C) {
			if (dist[y][i] == dist[y][z] + dist[z][i]) {
				s[i] = s[z] + dist[z][i];
				t[i] = TYPE_D;
				return;
			}
		}

		for (int z : rights_D) {
			if (dist[x][i] == dist[x][z] + dist[z][i]) {
				s[i] = s[z] - dist[z][i];
				t[i] = TYPE_C;
				return;
			}
		}
	}();
}

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