Submission #294996

#	Time	Username	Problem	Language	Result	Execution time	Memory
294996		mieszko11b	Rail (IOI14_rail)	C++14	100 / 100	1561 ms	1912 KiB

rail

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

using namespace std;

using ii = pair<int, int>;

#define X first
#define Y second

map<ii, int> M;

int dist(int a, int b) {
	if(a > b) swap(a, b);
	if(M.count({a, b}))
		return M[{a, b}];
	return M[{a, b}] = getDistance(a, b);
}

void findLocation(int N, int first, int location[], int stype[]) {
	for(int i = 0 ; i < N ; i++)
		stype[i] = location[i] = 0;
	
	stype[0] = 1;
	location[0] = first;
	
	int b = 1;
	for(int i = 2 ; i < N ; i++)
		if(dist(0, i) < dist(0, b))
			b = i;
	stype[b] = 2;
	location[b] = location[0] + dist(0, b);
	
	vector<int> lst;
	lst.push_back(b);
	int fst = 0;
	
	vector<ii> cand;
	for(int i = 0 ; i < N ; i++) {
		if(i == 0 || i == b)
			continue;
		int d0 = dist(0, i);
		int db = dist(b, i);
		int d = dist(0, b);
		
		if(d0 - db == d) {
			if(db < d)
				cand.push_back({d0, i});
		} else
			cand.push_back({d0, i});
	}
	
	sort(cand.begin(), cand.end());
	for(auto p : cand) {
		int d = dist(0, lst.back());
		int w = p.Y;
		int dlst = dist(lst.back(), w);
		bool ins = true;
		
		if(dlst >= d)
			ins = false;
		else {
			int ind = 0;
			while(dist(lst[ind], 0) < d - dlst)
				ind++;
			if(dist(lst[ind], 0) == d - dlst)
				ins = false;
			else {
				if(dist(0, lst[ind]) + (dist(0, lst[ind]) + dlst - d) != dist(0, w))
					ins = false;
			}
		}
		
		if(ins) {
			stype[w] = 1;
			location[w] = location[lst.back()] - dlst;
		} else {
			stype[w] = 2;
			location[w] = location[0] + dist(0, w);
			lst.push_back(w);
		}
	}
			
	int a = 0;
	for(int i = 1 ; i < N ; i++)
		if(i != b)
			if(dist(b, i) < dist(b, a))
				a = i;
	stype[a] = 1;
	location[a] = location[b] - dist(b, a);
	
	fst = b;
	lst.clear();
	lst.push_back(a);
	
	cand.clear();
	for(int i = 0 ; i < N ; i++) {
		if(stype[i])
			continue;
		cand.push_back({dist(fst, i), i});
	}
	
	sort(cand.begin(), cand.end());
	
	for(auto p : cand) {
		int d = dist(fst, lst.back());
		int w = p.Y;
		int dlst = dist(lst.back(), w);
		bool ins = true;
		
		if(dlst >= d)
			ins = false;
		else {
			int ind = 0;
			while(dist(lst[ind], fst) < d - dlst)
				ind++;
			if(dist(lst[ind], fst) == d - dlst)
				ins = false;
			else {
				if(dist(fst, lst[ind]) + (dist(fst, lst[ind]) + dlst - d) != dist(fst, w))
					ins = false;
			}
		}
		
		if(ins) {
			stype[w] = 2;
			location[w] = location[lst.back()] + dlst;
		} else {
			stype[w] = 1;
			location[w] = location[fst] - dist(fst, w);
			lst.push_back(w);
		}
	}	
	
	//~ for(int i = 0 ; i < N ; i++)
		//~ cout << stype[i] << " " << location[i] << endl;
	//~ cout << endl;
}

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