Submission #66968

#	Time	Username	Problem	Language	Result	Execution time	Memory
66968		Namnamseo	Rail (IOI14_rail)	C++17	30 / 100	122 ms	21556 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
using pp=pair<int,int>;
#define all(v) (v).begin(), (v).end()
#define pb push_back

int dcache[5000][5000];
int get_dist(int a, int b){
	if(dcache[a][b]) return dcache[a][b]-1;
	int d = getDistance(a, b);
	dcache[a][b] = d+1;
	return d;
}

vector<pp> ds;
vector<int> lv, rv;
void findLocation(int n, int first, int location[], int stype[])
{
	if(n == 1){
		location[0] = first;
		stype[0] = 1;
		return;
	}
	static bool first_run = true;
	if(!first_run) memset(dcache, -1, sizeof(dcache)), ds.clear(), lv.clear(), rv.clear();
	first_run = false;

	for(int i=1; i<n; ++i) ds.emplace_back(get_dist(0, i), i);
	sort(all(ds));

	int diam, ri;
	tie(diam, ri) = ds[0];
	int rp = first + diam;

	location[0] = first; stype[0] = 1;
	location[ri] = rp; stype[ri] = 2;

	for(int i=1; i<n; ++i) if(i != ri){
		int dl = get_dist(0, i);
		int dr = get_dist(ri, i);

		if(dr < diam && dl == diam + dr){
			location[i] = rp - dr;
			stype[i] = 1;
			continue;
		}

		if(dl == dr + diam) lv.pb(i);
		else rv.pb(i);
	}

	int lp = first, li = 0;
	for(int i : lv){
		int ld = get_dist(li, i);
		if(get_dist(ri, i) == (rp-lp) + ld){
			location[i] = lp + ld;
			stype[i] = 2;
		} else {
			lp = location[i] = rp - get_dist(ri, i);
			stype[i] = 1;
			li = i;
		}
	}

	for(int i : rv){
		int rd = get_dist(ri, i);
		if(get_dist(0, i) == (rp-first) + rd){
			location[i] = rp - rd;
			stype[i] = 1;
		} else {
			rp = location[i] = first + get_dist(0, i);
			stype[i] = 2;
			ri = i;
		}
	}
}

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