Submission #101880

#	Time	Username	Problem	Language	Result	Execution time	Memory
101880		eriksuenderhauf	Rail (IOI14_rail)	C++11	100 / 100	135 ms	31964 KiB

rail

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "rail.h"
//#include "grader.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 5e3 + 5;
const double eps = 1e-9;
int dp[MAXN][MAXN];
map<int,int> inv;

int dist(int x, int y) {
	if (x == y)
		return 0;
	if (x > y)
		swap(x, y);
	if (dp[x][y] == 0)
		dp[x][y] = getDistance(x, y);
	return dp[x][y];
}

void solve(int l[], int s[], vi& x, int st, int en) {
	sort(x.begin(), x.end(), [&](int l, int r) {
		return dist(st, l) < dist(st, r);
	});
	int sgn;
	if (s[st] == 1) // ((
		sgn = -1;
	else // ()
		sgn = 1;
	for (auto& t: x) {
		int val = (dist(en, t) + dist(st, en) - dist(st, t)) / 2;// get from en to en over the next free station
		val = l[en] + sgn * val;
		if (inv[val] == s[en]) {
			l[t] = val + sgn * (dist(st, t) - abs(l[st] - val));
			s[t] = s[st];
		} else {
			l[t] = l[st] - sgn * dist(st, t);
			s[t] = s[en];
			en = t;
		}
		inv[l[t]] = s[t];
	}
}

void findLocation(int n, int f, int l[], int s[]) {
	l[0] = f, s[0] = 1;
	inv[l[0]] = 1;
	if (n == 1)
		return;
	int pt = 1; // go the right
	for (int i = 2; i < n; i++)
		if (dist(0, pt) > dist(0, i))
			pt = i;
	l[pt] = l[0] + dist(0, pt);
	s[pt] = 2;
	inv[l[pt]] = 2;
	vi x, y;
	for (int i = 1; i < n; i++) {
		if (i == pt)
			continue;
		if (dist(pt, i) + dist(pt, 0) == dist(0, i)) {
			if (dist(pt, 0) > dist(pt, i)) { // case: (()
				l[i] = l[0] + dist(pt, 0) - dist(pt, i);
				s[i] = 1;
				inv[l[i]] = 1;
			} else { // )() and (() are possible
				x.pb(i);
			}
		} else {//()); if pt comes before 0 -> (() or ((( is possible
			y.pb(i);
		}
	}
	solve(l, s, x, pt, 0);
	solve(l, s, y, 0, pt);
}

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