Submission #49560

#	Time	Username	Problem	Language	Result	Execution time	Memory
49560		khsoo01	Rail (IOI14_rail)	C++11	100 / 100	149 ms	32272 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
const int M = 5005, inf = 1e9;

int d[M][M], p;

map<int,int> inv;

int getd (int I, int J) {
	if(I == J) return 0;
	if(I > J) swap(I, J);
	if(!d[I][J]) d[I][J] = getDistance(I, J);
	return d[I][J];
}

bool cmp (int A, int B) {
	return getd(p, A) < getd(p, B);
}

void solve (int L[], int S[], vector<int> &X, int P, int Q) {
	p = P;
	sort(X.begin(), X.end(), cmp);
	int D = (1 - 2 * (S[P] == 1));
	for(auto &T : X) {
		int V = (getd(Q, T) + getd(P, Q) - getd(P, T)) / 2;
		int C = L[Q] + D * V;
		if(inv[C] == S[Q]) {
			L[T] = C + D * (getd(P, T) - abs(L[P] - C));
			S[T] = S[P];
		}
		else {
			L[T] = L[P] - D * getd(P, T);
			S[T] = S[Q];
			Q = T;
		}
		inv[L[T]] = S[T];
	}
}

void findLocation(int N, int F, int L[], int S[])
{
	L[0] = F;
	S[0] = 1;
	inv[L[0]] = 1;
	if(N == 1) return;
	int I = 0, V = inf;
	for(int i=1; i<N; i++){
		int T = getd(0, i);
		if(V > T) {
			I = i;
			V = T;
		}
	}
	L[I] = L[0] + getd(0, I);
	S[I] = 2;
	inv[L[I]] = 2;
	vector<int> X, Y;
	for(int i=1; i<N; i++) {
		if(i == I) continue;
		if(getd(I, i) + getd(I, 0) == getd(0, i)) {
			if(getd(I, 0) > getd(I, i)) {
				L[i] = L[0] + getd(I, 0) - getd(I, i);
				S[i] = 1;
				inv[L[i]] = 1;
			}
			else X.push_back(i);
		}
		else Y.push_back(i);
	}
	solve(L, S, X, I, 0);
	solve(L, S, Y, 0, I);
}

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