제출 #799355

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
799355		Sohsoh84	철로 (IOI14_rail)	C++17	100 / 100	70 ms	32008 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], pos[MAXN], TTop[MAXN], Q;
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]) {
		assert(Q < 3 * (n - 1));
		D[i][j] = getDistance(i, j); // fuck
		Q++;
	}

	return D[i][j];
}

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

	map<int, int> mp;

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

	int lst = vec.front();
	vec.erase(vec.begin());
	pos[s] = 0;
	pos[lst] = get(s, lst);
	TTop[lst] = 1;
	mp[pos[lst]] = lst;
	mp[pos[s]] = s; // fuck

	for (int e : vec) {
		int poss = pos[lst] - get(lst, e);
		bool flag = true;
		if (poss <= pos[s]) flag = false;

		int t = get(s, e) - poss;
		if (!flag || t < 0 || t % 2) flag = false;
		else {
			t /= 2;
			int tpos = poss + t;
			if (mp.find(tpos) == mp.end()) flag = false;
			else flag = TTop[mp[tpos]];
		}

		flag ^= 1;
		TTop[e] = flag;
	
		if (TTop[e] == 0) pos[e] = pos[lst] - get(e, lst);
		else {
			lst = e;
			pos[e] = pos[s] + get(s, e);
		}

		mp[pos[e]] = e;
	}
}

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 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: 26 / 26
• Subtask 4: 44 / 44