oj.uz

Submission #610317

# Submission time Handle Problem Language Result Execution time Memory
610317 2022-07-28T06:35:34 Z KoD Sky Walking (IOI19_walk) C++17
0 / 100
 501 ms 47120 KB 
#include "walk.h"
#include <bits/stdc++.h>

using ll = long long;
using std::pair;
using std::vector;

template <class T>
using min_heap = std::priority_queue<T, vector<T>, std::greater<T>>;

ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int src, int dst) {
	const int N = (int)X.size();
	for (const int pivot : {src, dst}) {
		const int M = (int)Y.size();
		vector<pair<int, int>> left, right;
		for (int i = pivot; i >= 0; --i) {
			if (left.empty() or left.back().first < H[i]) {
				left.emplace_back(H[i], i);
			}
		}
		for (int i = pivot; i < N; ++i) {
			if (right.empty() or right.back().first < H[i]) {
				right.emplace_back(H[i], i);
			}
		}
		for (int i = 0; i < M; ++i) {
			if (L[i] < pivot and pivot < R[i]) {
				const int a = std::lower_bound(left.begin(), left.end(), pair(Y[i], 0))->second;
				const int b = std::lower_bound(right.begin(), right.end(), pair(Y[i], 0))->second;
				L.push_back(L[i]);
				R.push_back(a);
				Y.push_back(Y[i]);
				L.push_back(b);
				R.push_back(R[i]);
				Y.push_back(Y[i]);
				L[i] = a;
				R[i] = b;
			}
		}
	}
	vector<vector<pair<int, int>>> graph(N);
	const auto add_vertex = [&] {
		graph.emplace_back();
		return (int)graph.size() - 1;
	};
	const auto add_edge = [&](const int u, const int v, const int c) {
		graph[u].emplace_back(v, c);
		graph[v].emplace_back(u, c);
	};
	vector<vector<pair<int, int>>> vertices(N);
	for (int i = 0; i < N; ++i) {
		vertices[i].emplace_back(0, i);
	}
	const int M = (int)Y.size();
	vector<int> order(M);
	std::iota(order.begin(), order.end(), 0);
	std::sort(order.begin(), order.end(), [&](const int i, const int j) {
		return Y[i] > Y[j];
	});
	std::map<int, int> important;
	for (const int e : order) {
		if (L[e] == R[e]) {
			continue;
		}
		const int lu = add_vertex();
		vertices[L[e]].emplace_back(Y[e], lu);
		important[L[e]] = lu;
		const int ru = add_vertex();
		vertices[R[e]].emplace_back(Y[e], ru);
		important[R[e]] = ru;
		auto itr = important.upper_bound(L[e]);
		while (true) {
			const auto& [a, u] = *std::prev(itr);
			const auto& [b, v] = *itr;
			add_edge(u, v, X[b] - X[a]);
			if (itr->first == R[e]) {
				break;
			} else {
				itr = important.erase(itr);
			}
		}
	}
	std::set<int> remain;
	for (int i = 0; i < N; ++i) {
		remain.insert(i);
	}
	std::reverse(order.begin(), order.end());
	for (const int e : order) {
		if (L[e] == R[e]) {
			continue;
		}
		vector<int> list;
		list.push_back(L[e]);
		for (auto itr = remain.upper_bound(L[e]); itr != remain.end() and *itr < R[e]; itr = remain.erase(itr)) {
			if (Y[e] <= H[*itr]) {
				list.push_back(*itr);
			}
		}
		list.push_back(R[e]);
		const int n = (int)list.size();
		vector<int> id(n);
		for (int i = 0; i < n; ++i) {
			id[i] = add_vertex();
			vertices[list[i]].emplace_back(Y[e], id[i]);
		}
		for (int i = 0; i + 1 < n; ++i) {
			add_edge(id[i], id[i + 1], X[list[i + 1]] - X[list[i]]);
		}
	}
	for (auto& vec : vertices) {
		std::sort(vec.begin(), vec.end());
		const int n = (int)vec.size();
		for (int i = 0; i + 1 < n; ++i) {
			add_edge(vec[i].second, vec[i + 1].second, vec[i + 1].first - vec[i].first);
		}
	}
	vector<ll> dist(graph.size(), std::numeric_limits<ll>::max());
	min_heap<pair<ll, int>> heap;
	const auto push = [&](const int u, const ll d) {
		if (dist[u] > d) {
			dist[u] = d;
			heap.emplace(d, u);
		}
	};
	push(src, 0);
	while (!heap.empty()) {
		const auto [d, u] = heap.top();
		heap.pop();
		if (d > dist[u]) {
			continue;
		}
		for (const auto& [v, c] : graph[u]) {
			push(v, d + c);
		}
	}
	const ll ret = dist[dst];
	return ret == std::numeric_limits<ll>::max() ? -1 : ret;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 228 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 23348 KB Output is correct
2 Incorrect 501 ms 47120 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 23348 KB Output is correct
2 Incorrect 501 ms 47120 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -