제출 #282625

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

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5000 + 10;
int dis[maxn], a[maxn];
bool mark[maxn];
int loc[maxn], type[maxn];

set<pair<int,int>> S[3];

int dist[maxn][maxn];

int getDis(int x, int y){
	if (dist[x][y] != 0)
		return dist[x][y];
	int ret = getDistance(x,y);
	dist[x][y] = dist[y][x] = ret;
	assert(ret > 0);
	return ret;
}

int getL(int i){
	auto it = (S[1].lower_bound(make_pair(loc[i],-1)));
	it --;
	return (*it).second;
}

int getR(int i){
	return (*S[2].lower_bound(make_pair(loc[i],-1))).second;
}

void findLocation(int n, int first, int location[], int stype[]){
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			dist[i][j] = 0;
	loc[0] = first, type[0] = 1;
	if (n == 1)
		return;
	for (int i = 1; i < n; i++)
		dis[i] = getDis(0,i);
	for (int i = 1; i < n; i++)
		a[i] = i;
	sort(a+1, a+n, [](int a, int b){
		return dis[a] < dis[b];
	});
	S[1].insert({first,0});
	S[2].insert({first+dis[a[1]],a[1]});
	loc[a[1]] = first+dis[a[1]], type[a[1]] = 2;
	mark[0] = mark[a[1]] = 1;
	for (int _ = 2; _ < n; _++){
		int i = a[_];
		int end = (*S[2].rbegin()).second;
		loc[i] = loc[end]-getDis(end,i), type[i] = 1;
		if (loc[i] > first){
			int R = getR(i);
			if (getDis(0,i) != getDis(0,R) + getDis(R,i))
				loc[i] = loc[0] + getDis(0,i), type[i] = 2;
			S[type[i]].insert({loc[i],i});
			continue;
		}
		if (getDis(getR(0),i) > getDis(0,i)){
			loc[i] = loc[0] + getDis(0,i), type[i] = 2;
			S[type[i]].insert({loc[i],i});
			continue;
		}
		int beg = (*S[1].begin()).second;
		loc[i] = loc[beg]+getDis(beg,i), type[i] = 2;
		if (loc[i] < loc[getR(0)]){
			int L = getL(i);
			if (getDis(getR(0),i) != getDis(getR(0),L) + getDis(L,i))
				loc[i] = loc[getR(0)] - getDis(getR(0),i), type[i] = 1;
		}
		else
			loc[i] = loc[getR(0)] - getDis(getR(0),i), type[i] = 1; 
		S[type[i]].insert({loc[i],i});
	}
	for (int i = 0; i < n; i++)
		location[i] = loc[i], stype[i] = type[i];
}

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