Submission #114376

#	Time	Username	Problem	Language	Result	Execution time	Memory
114376		tjd229	Rail (IOI14_rail)	C++14	30 / 100	100 ms	34548 KiB

rail

#include "rail.h"
#include <vector>
#include <algorithm>
#define pii pair<int,int>
using namespace std;
int d[5000][5000];
int getDist(int i,int j) {
	if (!d[i][j])
		d[i][j] = d[j][i] = getDistance(i,j);
	return d[i][j];
}
void findLocation(int N, int first, int location[], int stype[])
{
	int i; location[0] = first; stype[0] = 1;
	vector<pii > v;
	for (i = 1; i < N; ++i) {
		v.push_back({getDist(0,i),i});
	}
	sort(v.begin(), v.end());
	int r = v[0].second; // right dtype
	int l = 0; //left ctype
	location[r] = v[0].first + first;
	stype[r] = 2;
	int fi = r; //first_dtype
	for (i = 1, --N; i < N; ++i) {//v_size==N-1
		int d0 = v[i].first;
		int x = v[i].second;
		int df = getDist(x,fi);
		if (df < d0) {
			if (getDist(0, r) + getDist(r, x) == getDist(0, x)) {
				stype[x] = 1;
				location[x]=location[r]-getDist(r,x);
			}
			else {
				stype[x] = 2;
				location[x] = first + getDist(0,x);
				r = x;
			}
		}
		else {
			if (getDist(fi, l) + getDist(x, l) == getDist(fi, x)) {
				stype[x] = 2;
				location[x] = location[l] + getDist(l, x);
			}
			else {
				stype[x] = 1;
				location[x] = location[fi] - getDist(fi,x);
				l = x;
			}
		}
	}
}

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