Submission #602337

#	Time	Username	Problem	Language	Result	Execution time	Memory
602337		farhan132	Rail (IOI14_rail)	C++17	30 / 100	104 ms	98552 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>

using namespace std;
 
typedef int ll;
typedef pair<ll , ll> ii;
 
#define ff first
#define ss second
#define pb push_back
#define in insert


const ll N = 5005;

ll dist[N][N];

ll D(ll i, ll j){
	if(i == j) return 0;
	if(dist[i][j] != -1) return dist[i][j];
	dist[i][j] = dist[j][i] = getDistance(i, j);
	return dist[i][j];
}

void findLocation(int n, int first, int location[], int stype[]){

	memset(dist, -1, sizeof(dist));

	ii mn = {1e9, 0};
	location[0] = first; stype[0] = 1;
	if(n == 1) return;

	for(ll i = 1; i < n; i++){
		mn = min(mn, {D(0, i), i});
	}

	ll D_block = mn.ss; ll C_block = 0;
	location[D_block] = first + mn.ff;
	stype[D_block] = 2;

	vector < ll > before, middle, after;

	for(ll i = 0; i < n; i++){
		if(i == D_block || i == C_block) continue;
		ll y = D(D_block, i);
		ll x = D(C_block, i);
		ll z = D(C_block, D_block);
		if(x - y == z && y > z) before.pb(i);
		else{
			if(y < z && x == y + z){
				middle.pb(i);
				stype[i] = 1;
				location[i] = location[D_block] - y;
			}else after.pb(i); 
		}
	}

	sort(before.begin(), before.end(), [&](ll i, ll j){
		return D(D_block, i) < D(D_block, j);
	});
	sort(after.begin(), after.end(), [&](ll i, ll j){
		return D(C_block, i) < D(C_block, j);
	});
	ll last = -1;
	//cout << before.size() << ' ' << middle.size() << ' ' << after.size() << '\n';
	for(auto i : after){
		if(last == -1){
			location[i] = location[C_block] + D(C_block, i);
			stype[i] = 2;
			last = i;
			continue;
		}
		ll x = D(C_block, i);
		ll y = D(last, i);
		ll z = D(last, C_block);
		if(y < z && x == y + z){
			location[i] = location[last] - y;
			stype[i] = 1;
		}else{
			location[i] = location[C_block] + x;
			stype[i] = 2;
			last = i;
		}
	}
	last = -1;

	for(auto i : before){
		if(last == -1){
			location[i] = location[D_block] - D(D_block, i);
			stype[i] = 1;
			last = i;
			continue;
		}
		ll x = D(D_block, i);
		ll y = D(last, i);
		ll z = D(last, D_block);
		if(y < z && x == y + z){
			location[i] = location[last] + y;
			stype[i] = 2;
		}else{
			location[i] = location[D_block] - x;
			stype[i] = 1;
			last = i;
		}
	}

	return;

}

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