oj.uz

Submission #48304

# Submission time Handle Problem Language Result Execution time Memory
48304 2018-05-11T15:12:16 Z cheater2k Rail (IOI14_rail) C++17
100 / 100
 212 ms 98884 KB 
#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) {
		//cerr << "set " << id << ' ' << pos << ' ' << type << endl;
		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 < location[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 > location[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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 724 KB Output is correct
2 Correct 2 ms 872 KB Output is correct
3 Correct 3 ms 872 KB Output is correct
4 Correct 3 ms 872 KB Output is correct
5 Correct 2 ms 888 KB Output is correct
6 Correct 2 ms 928 KB Output is correct
7 Correct 2 ms 928 KB Output is correct
8 Correct 3 ms 1056 KB Output is correct
9 Correct 3 ms 1056 KB Output is correct
10 Correct 2 ms 1056 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1056 KB Output is correct
2 Correct 2 ms 1056 KB Output is correct
3 Correct 3 ms 1056 KB Output is correct
4 Correct 3 ms 1056 KB Output is correct
5 Correct 2 ms 1056 KB Output is correct
6 Correct 2 ms 1056 KB Output is correct
7 Correct 3 ms 1056 KB Output is correct
8 Correct 3 ms 1056 KB Output is correct
9 Correct 2 ms 1056 KB Output is correct
10 Correct 3 ms 1056 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 98812 KB Output is correct
2 Correct 194 ms 98812 KB Output is correct
3 Correct 212 ms 98812 KB Output is correct
4 Correct 197 ms 98812 KB Output is correct
5 Correct 176 ms 98812 KB Output is correct
6 Correct 174 ms 98812 KB Output is correct
7 Correct 192 ms 98812 KB Output is correct
8 Correct 176 ms 98812 KB Output is correct
9 Correct 188 ms 98812 KB Output is correct
10 Correct 182 ms 98812 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 98812 KB Output is correct
2 Correct 180 ms 98812 KB Output is correct
3 Correct 180 ms 98816 KB Output is correct
4 Correct 178 ms 98816 KB Output is correct
5 Correct 210 ms 98856 KB Output is correct
6 Correct 179 ms 98856 KB Output is correct
7 Correct 179 ms 98856 KB Output is correct
8 Correct 177 ms 98856 KB Output is correct
9 Correct 179 ms 98856 KB Output is correct
10 Correct 181 ms 98876 KB Output is correct
11 Correct 184 ms 98876 KB Output is correct
12 Correct 173 ms 98876 KB Output is correct
13 Correct 173 ms 98876 KB Output is correct
14 Correct 168 ms 98876 KB Output is correct
15 Correct 176 ms 98884 KB Output is correct
16 Correct 207 ms 98884 KB Output is correct
17 Correct 177 ms 98884 KB Output is correct
18 Correct 180 ms 98884 KB Output is correct
19 Correct 184 ms 98884 KB Output is correct
20 Correct 191 ms 98884 KB Output is correct