Submission #8577

#	Time	Username	Problem	Language	Result	Execution time	Memory
8577		cki86201	Rail (IOI14_rail)	C++98	100 / 100	354 ms	968 KiB

rail

#include "rail.h"
#include<algorithm>
using namespace std;

typedef pair<int,int> Pi;
#define X first
#define Y second

int F[5050], T[5050];
Pi tF[5050], tT[5050];
int tf, tt;
int st[5050], top;
int val[5050];

void findLocation(int N, int first, int location[], int stype[])
{
	location[0] = first, stype[0] = 1;
	int i, tar = 1;
	for(i=1;i<N;i++){
		F[i] = getDistance(0, i);
		if(F[tar] > F[i])tar = i;
	}
	location[tar] = F[tar] + first;
	stype[tar] = 2;
	for(i=1;i<N;i++)if(i != tar)T[i] = getDistance(tar, i);
	for(i=1;i<N;i++){
		if(i == tar)continue;
		if(F[i] == T[i] + F[tar])tT[tt++] = Pi(T[i], i);
		else tF[tf++] = Pi(F[i] - F[tar], i);
	}
	sort(tT, tT+tt);
	sort(tF, tF+tf);
	if(tt)val[tT[0].Y] = tT[0].X, stype[tT[0].Y] = 1;
	st[top++] = tT[0].Y;
	for(i=1;i<tt;i++){
		int t = getDistance(tT[i].Y, st[top-1]), j;
		for(j=0;j<top;j++){
			int b = val[st[j]]*2 - tT[i].X;
			if(val[st[top-1]]-b == t)break;
		}
		if(j == top){
			val[tT[i].Y] = tT[i].X, stype[tT[i].Y] = 1;
			st[top++] = tT[i].Y;
		}
		else{
			val[tT[i].Y] = val[st[j]]*2 - tT[i].X, stype[tT[i].Y] = 2;
		}
	}
	for(i=0;i<tt;i++)location[tT[i].Y] = location[tar] - val[tT[i].Y];

	top = 0;
	if(tf)val[tF[0].Y] = tF[0].X, stype[tF[0].Y] = 2;
	st[top++] = tF[0].Y;
	for(i=1;i<tf;i++){
		int t = getDistance(tF[i].Y, st[top-1]), j;
		for(j=0;j<top;j++){
			int b = val[st[j]]*2 - tF[i].X;
			if(val[st[top-1]]-b == t)break;
		}
		if(j == top){
			val[tF[i].Y] = tF[i].X, stype[tF[i].Y] = 2;
			st[top++] = tF[i].Y;
		}
		else{
			val[tF[i].Y] = val[st[j]]*2 - tF[i].X, stype[tF[i].Y] = 1;
		}
	}
	for(i=0;i<tf;i++)location[tF[i].Y] = location[tar] + val[tF[i].Y];
}

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