Submission #294988

#	Time	Username	Problem	Language	Result	Execution time	Memory
294988		mieszko11b	Rail (IOI14_rail)	C++14	8 / 100	157 ms	1272 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[]) {
	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);
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:33:6: warning: unused variable 'fst' [-Wunused-variable]
   33 |  int fst = 0;
      |      ^~~

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