Submission #798142

#	Time	Username	Problem	Language	Result	Execution time	Memory
798142		QwertyPi	Rail (IOI14_rail)	C++14	100 / 100	97 ms	1456 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
#define INF (1 << 30)
using namespace std;
 
int d0[5011], d1[5011];
 
map<pair<int, int>, int> M;
int sGetDistance(int i, int j){
	if(i > j) swap(i, j);
	if(i == j) return 0;
	if(M.count({i, j})) return M[{i, j}];
	return M[{i, j}] = getDistance(i, j);
}
void findLocation(int N, int first, int location[], int stype[]){
	for(int i = 1; i < N; i++) d0[i] = sGetDistance(0, i); int p0 = 0;
	int s = INF, p1; for(int i = 1; i < N; i++) if(d0[i] < s) s = d0[i], p1 = i;
	for(int i = 0; i < N; i++) if(i != p1) d1[i] = sGetDistance(p1, i);
	
	location[p0] = first; stype[p0] = 1;
	location[p1] = first + s; stype[p1] = 2;
	vector<int> L, R;
	for(int i = 0; i < N; i++){
		if(i != p0 && i != p1){
			if(d1[i] < s) location[i] = first + s - d1[i], stype[i] = 1;
			if(d0[i] - d1[i] == s) L.push_back(i);
			else R.push_back(i);
		}
	}
	sort(L.begin(), L.end(), [](int x, int y){ return d1[x] < d1[y]; });
	sort(R.begin(), R.end(), [](int x, int y){ return d0[x] < d0[y]; });
	int leftmost = p0;
	for(int l : L){
		int dis = sGetDistance(leftmost, l);
		location[l] = location[leftmost] + dis; stype[l] = 2;
		int leftBound = leftmost; for(int i = 0; i < N; i++) if(stype[i] == 1 && location[leftBound] <= location[i] && location[i] < location[l]) leftBound = i;
		if((location[leftBound] - location[leftmost]) * 2 == d1[leftmost] + dis - d1[l]){
			location[l] = location[leftmost] + dis; stype[l] = 2;
		}else{
			location[l] = location[p1] - d1[l]; stype[l] = 1;
			leftmost = l;
		}
	}
	
	int rightmost = p1;
	for(int r : R){
		int dis = sGetDistance(rightmost, r);
		location[r] = location[rightmost] - dis; stype[r] = 1;
		int rightBound = rightmost; for(int i = 0; i < N; i++) if(stype[i] == 2 && location[r] < location[i] && location[i] <= location[rightBound]) rightBound = i;
		if((location[rightmost] - location[rightBound]) * 2 == d0[rightmost] + dis - d0[r]){
			location[r] = location[rightmost] - dis; stype[r] = 1;
		}else{
			rightmost = r;
			location[r] = location[p0] + d0[r]; stype[r] = 2;
		}
	}
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:16:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   16 |  for(int i = 1; i < N; i++) d0[i] = sGetDistance(0, i); int p0 = 0;
      |  ^~~
rail.cpp:16:57: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   16 |  for(int i = 1; i < N; i++) d0[i] = sGetDistance(0, i); int p0 = 0;
      |                                                         ^~~
rail.cpp:24:14: warning: 'p1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   24 |   if(i != p0 && i != p1){
      |      ~~~~~~~~^~~~~~~~~~

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