Submission #799146

#	Time	Username	Problem	Language	Result	Execution time	Memory
799146		Sohsoh84	Rail (IOI14_rail)	C++17	30 / 100	66 ms	20604 KiB

rail

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)			(x).begin(), (x).end()
#define debug(x)		cerr << #x << ": " << x << endl;
#define sep			' '
#define X			first
#define Y			second

const ll MAXN = 5000 + 10;
const ll INF = 1e9 + 10;

int n, f, D[MAXN][MAXN], best[MAXN], best_par[MAXN], pos[MAXN], TTop[MAXN];
bool vis[MAXN];


inline int get(int i, int j) {
	if (i > j) swap(i, j);
	if (i == j) return 0;
	if (!D[i][j]) D[i][j] = getDistance(i, j); // fuck
	return D[i][j];
}

inline int is_mid(int a, int b, int v) {
	return get(a, v) >= get(a, b) + get(b, v);
}

inline void solve(int s, vector<int> vec) {
	if (vec.empty()) return;

	sort(all(vec), [s] (int i, int j) {
		return get(s, i) < get(s, j);
	});

	int lst = vec.front();
	vec.erase(vec.begin());
	pos[lst] = get(s, lst);

	for (int e : vec) {
		if (is_mid(s, lst, e)) {
			pos[e] = pos[lst] - get(e, lst);
			TTop[e] = 0;
		} else {
			pos[e] = get(s, e);
			lst = e;
			TTop[e] = 1;
		}
	}
}

void findLocation(int N, int first, int location[], int stype[]) {
	n = N;
	f = first;
	location[0] = f;
	stype[0] = 0;
	if (n == 1) return;
	
	int mn = 1;
	for (int i = 1; i < n; i++)
		if (get(0, i) < get(0, mn))
			mn = i;

	vector<int> P[2];
	for (int i = 0; i < n; i++) {
		if (i == 0 || i == mn) continue;
		P[int(get(0, i) == get(0, mn) + get(mn, i))].push_back(i);
	}

	P[0].push_back(mn);
	P[1].push_back(0);
	location[mn] = location[0] + get(0, mn);
	stype[mn] = 1;

	solve(0, P[0]);
	solve(mn, P[1]);

	for (int e : P[0]) {
		if (e != 0 && e != mn) {
			location[e] = location[0] + pos[e];
			stype[e] = stype[0] ^ TTop[e];
		}
	}

	for (int e : P[1]) {
		if (e != 0 && e != mn) {
			location[e] = location[mn] - pos[e];
			stype[e] = stype[mn] ^ TTop[e];
		}
	}

	for (int e : P[0]) debug(e)

	for (int i = 0; i < n; i++)
		stype[i]++;
/*
	for (int i = 0; i < n; i++) cerr << location[i] << sep;
	cerr << endl;
	for (int i = 0; i < n; i++) cerr << stype[i] << sep;
	cerr << endl;
*/
}

// mn location

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