Submission #48302

#	Time	Username	Problem	Language	Result	Execution time	Memory
48302		cheater2k	Rail (IOI14_rail)	C++17	30 / 100	203 ms	98952 KiB

rail

#include "rail.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 5005; 
const int inf = 1e9; 

int dis[maxn][maxn];

void findLocation(int n, int first, int location[], int stype[]) {
	auto set_type = [&](int id, int pos, int type) {
		assert(pos >= 0 && pos <= 1000000);
		location[id] = pos;
		stype[id] = type;
	};

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			dis[i][j] = (i == j) ? 0 : -1;
		}
	}

	int d, mn = inf;
	set_type(0, first, 1);
	for (int i = 1; i < n; ++i) {
		dis[0][i] = getDistance(0, i);
		if (dis[0][i] < mn) {
			mn = dis[0][i], d = i; // d is of type D, which is nearest to station 0
		}
	}
	dis[d][0] = dis[0][d];
	set_type(d, dis[0][d] + first, 2);

	for (int i = 1; i < n; ++i) if (i != d) {
		dis[d][i] = getDistance(d, i);
	}

	// SOLVE
	vector < pair<int,int> > lef, rig;
	for (int i = 0; i < n; ++i) {
		if (i != d) {
			if (i == 0 || dis[0][i] == dis[0][d] + dis[d][i]) {
				lef.push_back({dis[d][i], i});
			} else {
				rig.push_back({dis[0][i], i});
			}
		}
	}
	sort(lef.begin(), lef.end());
	sort(rig.begin(), rig.end());

	// printf("lef\n");
	// for (auto &p : lef) printf("%d %d\n", p.first, p.second);
	// printf("rig\n");
	// for (auto &p : rig) printf("%d %d\n", p.first, p.second);

	/* SOLVE LEFT SIDE */
	set < pair<int,int> > down;
	for (auto &p : lef) {
		// whether this station is of type C or type D?
		// D?
		bool ok = false;
		if (!down.empty()) {
			auto lastC = (*down.begin());
			dis[p.second][lastC.second] = getDistance(p.second, lastC.second);
			int plocation = lastC.first + dis[p.second][lastC.second];

			if (plocation < d) {
				// find the nearest C
				set < pair<int,int> >::iterator it = down.lower_bound({plocation, 0});
				if (it != down.begin()) {
					--it;
					auto nearestC = (*it);
					if (plocation - nearestC.first + dis[d][nearestC.second] == p.first) {
						// check shortest path from d
						ok = true;
						set_type(p.second, plocation, 2); // type D
					}
				}
			}
		}
		// C?
		if (!ok) {
			set_type(p.second, location[d] - p.first, 1);
			down.insert({location[d] - p.first, p.second});
		}
	}

	/* SOLVE RIGHT SIDE */
	set < pair<int,int> > up;
	for (auto &p : rig) {
		// whether this station is of type C or type D?
		// C?
		bool ok = false;
		if (!up.empty()) {
			auto lastD = (*up.rbegin());
			dis[p.second][lastD.second] = getDistance(p.second, lastD.second);
			int plocation = lastD.first - dis[p.second][lastD.second];

			if (plocation > d) {
				// find the nearest D
				set < pair<int,int> >::iterator it = up.upper_bound({plocation, inf});
				if (it != up.end()) {
					auto nearestD = (*it);
					if (nearestD.first - plocation + dis[0][nearestD.second] == p.first) {
						// check shortest path from 0
						ok = true;
						set_type(p.second, plocation, 1); // type C
					}
				}
			}
		}
		// D?
		if (!ok) {
			set_type(p.second, location[0] + p.first, 2);
			up.insert({location[0] + p.first, p.second});
		}
	}
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:13:14: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
   location[id] = pos;
              ^

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