Submission #145197

#	Time	Username	Problem	Language	Result	Execution time	Memory
145197		ecnerwala	Sky Walking (IOI19_walk)	C++14	100 / 100	1565 ms	132924 KiB

walk

#include "walk.h"

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using height_t = pair<int, int>;

ll min_distance(vector<int> X_, vector<int> H_, vector<int> L, vector<int> R, vector<int> Y_, int S, int T) {
	int N = int(X_.size());
	int M = int(Y_.size());

	vector<ll> X(X_.begin(), X_.end());
	vector<height_t> H(N);
	for (int i = 0; i < N; i++) {
		H[i] = {H_[i], i};
	}

	vector<height_t> Y(M);
	for (int e = 0; e < M; e++) {
		Y[e] = {Y_[e], -1-e};
	}

	vector<vector<height_t>> needs(N);

	vector<height_t> heights;
	heights.insert(heights.end(), H.begin(), H.end());
	heights.insert(heights.end(), Y.begin(), Y.end());
	sort(heights.begin(), heights.end());
	reverse(heights.begin(), heights.end());

	set<int> posts;
	for (height_t h : heights) {
		if (h.second >= 0) {
			// it's a post
			posts.insert(h.second);
		} else {
			int e = -1-h.second;
			set<int> eNeeds;
			eNeeds.insert(L[e]);
			eNeeds.insert(R[e]);
			for (int p : {S, T}) {
				if (L[e] <= p && p <= R[e]) {
					{
						auto it = posts.lower_bound(p);
						if (it != posts.end()) {
							eNeeds.insert(*it);
						}
					}
					{
						auto it = posts.upper_bound(p);
						if (it != posts.begin()) {
							eNeeds.insert(*--it);
						}
					}
				}
			}
			for (int i : eNeeds) {
				needs[i].push_back(h);
			}
		}
	}

	int V = 0;
	vector<vector<pair<int, ll>>> adj;

	map<height_t, pair<int, int>> prvVert;
	set<height_t> inters;
	vector<vector<height_t>> lefts(N);
	vector<vector<height_t>> rights(N);
	for (int e = 0; e < M; e++) {
		lefts[L[e]].push_back(Y[e]);
		rights[R[e]].push_back(Y[e]);
	}

	const height_t SBOTTOM(0, -1-M);
	lefts[S].push_back(SBOTTOM);
	rights[S].push_back(SBOTTOM);
	needs[S].push_back(SBOTTOM);

	const height_t TBOTTOM(0, -1-(M+1));
	lefts[T].push_back(TBOTTOM);
	rights[T].push_back(TBOTTOM);
	needs[T].push_back(TBOTTOM);


	int Svert = -1, Tvert = -1;
	for (int i = 0; i < N; i++) {
		for (height_t h : lefts[i]) {
			inters.insert(h);
		}

		reverse(needs[i].begin(), needs[i].end()); // should now be sorted

		vector<height_t> realNeeds;
		for (height_t h : needs[i]) {
			auto it = inters.find(h);
			assert(it != inters.end());

			auto kt = it;
			if (kt != inters.begin()) {
				--kt;
				if (realNeeds.empty() || realNeeds.back() < *kt) {
					realNeeds.push_back(*kt);
				}
			}

			if (realNeeds.empty() || realNeeds.back() < *it) {
				realNeeds.push_back(*it);
			}

			auto jt = it; ++jt;
			if (jt != inters.end()) {
				if (realNeeds.empty() || realNeeds.back() < *jt) {
					realNeeds.push_back(*jt);
				}
			}
		}

		while (!realNeeds.empty() && realNeeds.back() > H[i]) realNeeds.pop_back();

		assert(V == int(adj.size()));
		adj.resize(V + int(realNeeds.size()));

		for (int z = 0; z < int(realNeeds.size()); z++) {
			height_t h = realNeeds[z];
			int v = V + z;

			auto it = prvVert.find(h);
			if (it != prvVert.end()) {
				int u = it->second.second;
				ll d = X[i] - X[it->second.first];
				adj[v].emplace_back(u, d);
				adj[u].emplace_back(v, d);

				it->second = {i, v};
			} else {
				prvVert.emplace(h, pair<int, int>{i, v});
			}
		}

		for (int z = 0; z+1 < int(realNeeds.size()); z++) {
			assert(realNeeds[z] < realNeeds[z+1]);
			int v = V + z + 1;
			int u = V + z;
			ll d = realNeeds[z+1].first - realNeeds[z].first;
			adj[v].emplace_back(u, d);
			adj[u].emplace_back(v, d);
		}

		if (i == S) {
			assert(!realNeeds.empty());
			assert(realNeeds[0] == SBOTTOM);
			Svert = V + 0;
		}
		if (i == T) {
			assert(!realNeeds.empty());
			assert(realNeeds[0] == TBOTTOM);
			Tvert = V + 0;
		}

		V += int(realNeeds.size());

		for (height_t h : rights[i]) {
			inters.erase(h);
		}
	}

	const ll INF = 1e18;
	vector<ll> dist(V, INF);
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
	dist[Svert] = 0;
	pq.emplace(0, Svert);
	while (!pq.empty()) {
		int cur = pq.top().second;
		ll d = pq.top().first;
		pq.pop();
		if (dist[cur] != d) continue;

		if (cur == Tvert) return d;

		for (auto it : adj[cur]) {
			int nxt = it.first;
			ll nd = d + it.second;
			if (nd < dist[nxt]) {
				dist[nxt] = nd;
				pq.emplace(nd, nxt);
			}
		}
	}

	return -1;
}

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 43 / 43