제출 #1064459

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1064459		Mr_Husanboy	Rail (IOI14_rail)	C++17	30 / 100	78 ms	98444 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()

template<typename T>
int len(T &a){
	return a.size();
}

const int maxn = 5e3;
const int inf = 1e9;

int memo[maxn][maxn];

int get(int i, int j){
	if(i == j) return 0;
	if(memo[i][j] != -1){
		return memo[i][j];
	}
	return memo[i][j] = memo[j][i] = getDistance(i, j);
}

void findLocation(int n, int first, int location[], int stype[])
{
	for(int i = 0; i < n; i ++){
		location[i] = -1;
		for(int j = 0; j < n; j ++){
			memo[i][j] = -1;
		}
	}
	location[0] = first;
	stype[0] = 1;
	if(n == 1){
		return;
	}
	int rig = 0, mn = inf + 1;
	for(int i = 1; i < n; i ++){
		if(get(0, i) < mn){
			mn = get(0, i);
			rig = i;
		}
	}

	int lef = 0;
	mn = get(0, rig);

	for(int i = 1; i < n; i ++){
		if(rig == i) continue;
		if(mn > get(rig, i)){
			mn = get(rig, i);
			rig = i;
		}
	}

	location[rig] = first + get(0, rig);
	stype[rig] = 2;
	location[lef] = location[rig] - get(rig, lef);
	stype[lef] = 1; 

	vector<pair<int,int>> lefs, rigs;

	for(int i = 0; i < n; i ++){
		if(location[i] != -1) continue;
		if(get(0, i) == get(0, rig) + get(rig, i)){
			lefs.push_back({get(0, i), i});
		}else{
			rigs.push_back({get(0, i), i});
		}
	}
	sort(all(rigs));
	sort(all(lefs));

	for(auto [d, i] : rigs){
		memo[lef][i] = memo[i][lef] = get(rig, i) - get(lef, rig);
	}
	int last = rig;
	for(auto [d, i] : rigs){
		if(get(lef, i) == get(last, i) + get(lef, last)){
			location[i] = location[last] - get(last, i);
			stype[i] = 1;
		}else{
			location[i] = location[lef] + get(lef, i);
			stype[i] = 2;
			last = i;
		}
	}
	last = lef;
	for(auto [d, i] : lefs){
		if(get(rig, i) == get(last, i) + get(rig, last)){
			location[i] = location[last] + get(last, i);
			stype[i] = 2;
		}else{
			location[i] = location[rig] - get(rig, i);
			stype[i] = 1;
			last = i;
		}
	}
}

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