Submission #50296

#	Time	Username	Problem	Language	Result	Execution time	Memory
50296		top34051	Rail (IOI14_rail)	C++17	56 / 100	847 ms	67968 KiB

rail

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

const int maxn = 5e3  + 5;

int pos;
int ban[maxn];
int rec[maxn][maxn];

int ask(int x, int y) {
	if(x>y) swap(x,y);
	if(!rec[x][y]) rec[x][y] = getDistance(x,y);
//	printf("\task %d %d = %d\n",x,y,rec[x][y]);
	return rec[x][y];
}

void findLocation(int N, int first, int location[], int stype[]) {
	//find right
	ban[0] = 1;
	while(1) {
		int x = -1;
		//nearest D
		for(int i=0;i<N;i++) {
			if(!ban[i] && (x==-1 || ask(0,i)<ask(0,x))) {
				x = i;
			}
		}
		if(x==-1) break;
		pos = x;
		ban[x] = 1;
		//sweep left
		for(int i=0;i<N;i++) {
			if(!ban[i] && ask(0,i)-ask(0,x)==ask(x,i)) {
				ban[i] = 1;
			}
		}
	}
	memset(ban,0,sizeof(ban));
	ban[pos] = 1;
	location[pos] = first + ask(0,pos);
	stype[pos] = 2;
	while(1) {
		int x = -1;
		//nearest C
		for(int i=0;i<N;i++) {
			if(!ban[i] && (x==-1 || ask(pos,i)<ask(pos,x))) {
				x = i;
			}
		}
		if(x==-1) break;
		ban[x] = 1;
		location[x] = location[pos] - ask(pos,x);
		stype[x] = 1;
//		printf("%d (%d): ",x,location[x]);
		//sweep right
		for(int i=0;i<N;i++) {
			if(!ban[i] && ask(pos,i)-ask(pos,x)==ask(x,i)) {
				ban[i] = 1;
				location[i] = location[x] + ask(x,i);
				stype[i] = 2;
//				printf("%d (%d) ",i,location[i]);
			}
		}
//		printf("\n");
	}
//	for(int i=0;i<N;i++) printf("%d %d\n",stype[i],location[i]);
}

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