Submission #586746

#	Time	Username	Problem	Language	Result	Execution time	Memory
586746		Tekor	Rail (IOI14_rail)	C++17	8 / 100	298 ms	71908 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair <int,int>
#define f first
#define s second
#define mp make_pair
const int N = 5e3 + 100;
const int INTmx = (int)1e9;
int a[N],b[N],n;
bool ban[N];
int sd[N];
bool was[N][N];
int c[N][N];
int get(int x,int y) {
	if(was[x][y])return c[x][y];
	was[x][y] = 1;
	c[x][y] = getDistance(x,y);
	return c[x][y];
}
void findLocation(int NN, int first, int location[], int stype[]) {
	n = NN;
	location[0] = first;
	stype[0] = 1;
	pii mn = mp(INTmx,0);
	int L = 0;
	ban[0] = 1;
	for(int i = 1;i < n;i++) {
		if(ban[i])continue;
		mn = min(mn,mp(get(L,i),i));
	}
	int R = mn.s;
	ban[R] = 1;
	location[R] = location[L] + get(L,R);
	stype[R] = 2;
	int kol = 2;
	for(int i = 1;i < n;i++) {
		if(ban[i])continue;
		if(get(L,i) == get(R,i) + get(L,R) && get(R,i) < get(L,R)) {
			stype[i] = 1;
			location[i] = location[R] - get(R,i);
			ban[i] = 1;
			kol++;
		}
	}
	//cout << R << " " << stype[R] << endl;
	while(kol < n) {
		mn = mp(INTmx,0);
		pii mn1 = mp(INTmx,0);
		for(int i = 1;i < n;i++) {
			if(ban[i])continue;
			mn = min(mn,mp(get(L,i),i));
			mn1 = min(mn1,mp(get(R,i),i));
		}
		if(get(R,mn.s) == get(L,mn.s) + get(L,R)) {
			kol++;
			R = mn.s;
			ban[R] = 1;
			//cout << "change R to " << R << endl;
			location[R] = location[L] + get(L,R);
			stype[R] = 2;
			for(int i = 1;i < n;i++) {
				if(ban[i])continue;
				if(get(L,i) == get(R,i) + get(L,R) && get(R,i) < get(L,R)) {
					stype[i] = 1;
					location[i] = location[R] - get(R,i);
					ban[i] = 1;
					kol++;
				}
			}
		}else {
			kol++;
			L = mn1.s;
			ban[L] = 1;
			//cout << "change L to " << L << endl;
			location[L] = location[R] - get(R,L);
			stype[L] = 1;
			for(int i = 1;i < n;i++) {
				if(ban[i])continue;
				if(get(R,i) == get(L,i) + get(R,L) && get(L,i) < get(R,L)) {
					stype[i] = 2;
					location[i] = location[L] + get(L,i);
					ban[i] = 1;
					kol++;
				}
			}
		}
		//cout << L << " " << R << endl;
	}
	
}

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