Submission #1197323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197323		stdfloat	Sky Walking (IOI19_walk)	C++20	10 / 100	4101 ms	197852 KiB

walk

#include <bits/stdc++.h>
#include "walk.h"
// #include "grader.cpp"
using namespace std;

using ll = long long;

#define sz(v)  (int)v.size()
#define all(v) v.begin(), v.end()

#define ff	first
#define ss	second
#define pii	pair<int, int>

ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int S, int G) {
	int n = sz(X), m = sz(L);

	vector<int> ordq(m);
	iota(all(ordq), 0);
	sort(all(ordq), [&](int x, int y) {
		return Y[x] < Y[y] || (Y[x] == Y[y] && x < y);
	});
	reverse(all(ordq));

	vector<int> ord(n);
	iota(all(ord), 0);
	sort(all(ord), [&](int x, int y) {
		return H[x] < H[y] || (H[x] == H[y] && x < y);
	});

	set<int> s;
	int ind = n - 1;
	vector<pii> E[n];
	for (auto i : ordq) {
		while (~ind && Y[i] <= H[ord[ind]]) s.insert(ord[ind--]);

		int x = L[i];
		while (x != R[i]) {
			// int y = -1;
			// for (int j = x + 1; j <= R[i] && !~y; j++)
			// 	if (Y[i] <= H[j]) y = j;

			// if (!~y) break;

			auto y = s.upper_bound(x);
			if (y == s.end()) break;

			E[x].push_back({x, Y[i]});
			E[x].push_back({*y, Y[i]});

			E[*y].push_back({*y, Y[i]}); //don't need?
			E[*y].push_back({x, Y[i]});

			x = *y;
		}
	}

	priority_queue<pair<ll, pii>> q;
	vector<map<int, ll>> dis(n);
	q.push({0, {S, 0}}); dis[S][0] = 0;
	while (!q.empty()) {
		auto [d, x] = q.top(); d = -d; q.pop();

		if (d != dis[x.ff][x.ss]) continue;

		for (auto [i, y] : E[x.ff]) {
			if (dis[i].find(y) == dis[i].end() || d + abs(x.ss - y) + abs(X[x.ff] - X[i]) < dis[i][y]) {
				dis[i][y] = d + abs(x.ss - y) + abs(X[x.ff] - X[i]);
				q.push({-dis[i][y], {i, y}});
			}
		}
	}

	if (dis[G].empty()) return -1;

	ll mn = LLONG_MAX;
	for (auto i : dis[G])
		mn = min(mn, i.ff + i.ss);

	return mn;
}

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