제출 #49520

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49520		Namnamseo	Rail (IOI14_rail)	C++17	8 / 100	132 ms	51696 KiB

rail

#include "rail.h"

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

using pp=pair<int,int>;
#define x first
#define y second
pp kyori[5010];

int dc[5010][5010];

int dst(int a, int b){
	if(dc[a][b]) return dc[a][b];
	return dc[a][b]=dc[b][a]=getDistance(a, b);
}

void findLocation(int n, int first, int location[], int stype[])
{
	for(int i=1; i<n; ++i) kyori[i-1]={dst(0, i), i};
	sort(kyori, kyori+n-1);
	int L = 0, Lp = first, R = kyori[0].y, Rp = Lp + kyori[0].x;
	location[L] = Lp;
	location[R] = Rp;
	stype[L] = 1; stype[R] = 2;
	for(int i=1; i<n-1; ++i){
		int j = kyori[i].y;
		int dl = dst(L, j), dr = dst(R, j);
		int jp;
		if(dl < dr){
			jp = Lp + dl;
			stype[j] = 2;
			if(jp > Rp){
				R = j;
				Rp = jp;
			}
		} else {
			jp = Rp - dr;
			stype[j] = 1;
			if(jp < Lp){
				L = j;
				Lp = jp;
			}
		}
		location[j] = jp;
	}
}

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