Submission #1023151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023151		AmirAli_H1	Rail (IOI14_rail)	C++17	30 / 100	41 ms	3156 KiB

rail

// In the name of Allah

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

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 5000 + 4;
const int maxs = 1e6 + 4;
const int oo = 1e9 + 7;

int n, Dx;
vector<pll> ls;
ll ansD[maxn], ansT[maxn];
bool mark[maxn]; pll d[maxn];
ll dis[maxn]; int val[maxs];

int getDistance(int u, int v);

void upd(int v) {
	for (int u = 0; u < n; u++) {
		if (mark[u]) continue;
		int x = getDistance(v, u);
		auto f = Mp(d[v].F + x, d[v].S - 1);
		if (f < d[u]) {
			if (ansT[v] == 1) {
				ansD[u] = ansD[v] + x; ansT[u] = 2;
			}
			else {
				ansD[u] = ansD[v] - x; ansT[u] = 1;
			}
			d[u] = f;
		}
	}
}

void solve1() {
	fill(mark, mark + n, 0); fill(d, d + n, Mp(oo, 0));
	
	int v = 0;
	ansD[v] = Dx; ansT[v] = 1;
	mark[v] = 1; d[v] = Mp(0, 0);
	upd(v);
	
	while (true) {
		int v = -1;
		for (int u = 0; u < n; u++) {
			if (mark[u]) continue;
			if (v == -1 || d[u] < d[v]) v = u;
		}
		if (v == -1) break;
		
		mark[v] = 1;
		upd(v);
	}
}

void solve2() {
	int v = 0; dis[v] = 0;
	ansD[v] = Dx; ansT[v] = 1;
	val[ansD[v]] = ansT[v];
	for (int u = 0; u < n; u++) {
		if (u == v) continue;
		dis[u] = getDistance(v, u);
		ls.pb(Mp(dis[u], u));
	}
	sort(all(ls));
	
	int u = ls[0].S;
	ansD[u] = ansD[v] + dis[u]; ansT[u] = 2;
	val[ansD[u]] = ansT[u];
	
	pii A = Mp(v, u);
	for (int i = 1; i < len(ls); i++) {
		int r = ls[i].S;
		ll D1 = getDistance(A.F, r), D2 = getDistance(A.S, r);
		
		ll x1 = dis[A.S] + D2, x2 = dis[r];
		ll dx = ansD[A.S] - ((x1 - x2) / 2);
		if (val[dx] == 1) {
			ansD[r] = ansD[v] + dis[r]; ansT[r] = 2;
		}
		else {
			if (ansD[A.S] - D2 >= ansD[v]) {
				ansD[r] = ansD[A.S] - D2; ansT[r] = 1;
			}
			else {
				if (abs(ansD[A.F] - ansD[u]) + getDistance(u, r) == D1) {
					ansD[r] = ansD[A.S] - D2; ansT[r] = 1;
				}
				else {
					ansD[r] = ansD[A.F] + D1; ansT[r] = 2;
				}
			}
		}
		
		val[ansD[r]] = ansT[r];
		if (ansD[r] < ansD[A.F]) A.F = r;
		if (ansD[r] > ansD[A.S]) A.S = r;
	}
}

void findLocation(int N, int D, int location[], int stype[]) {
	n = N; Dx = D;
	
	if (n <= 8) solve1();
	else solve2();
	
	for (int i = 0; i < n; i++) {
		location[i] = ansD[i];
		stype[i] = ansT[i];
	}
}

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