Submission #417277

#	Time	Username	Problem	Language	Result	Execution time	Memory
417277		Mlxa	Sky Walking (IOI19_walk)	C++14	10 / 100	4046 ms	370336 KiB

walk

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "walk.h"

namespace my {
const int N = 2e6 + 10;

int ff = 0;
vector<pair<int, int>> g[N];
vector<pair<int, int>> ys[N];

void edge(int v, int u, int w) {
	g[v].emplace_back(u, w);
	g[u].emplace_back(v, w);
}

using T = pair<ll, int>;
const ll INF = 1e18;
priority_queue<T, vector<T>, greater<T>> q;
ll dst[N];
int ground[N];

bool wastl = false;
int iter = 0;
bool istl() {
	if (wastl) {
		return true;
	}
	++iter;
	if (iter & 15) {
		return false;
	}
	return wastl = clock() > 3.9L * CLOCKS_PER_SEC;
}
}

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int st, int fi) {
	using namespace my;
	for (int i = 0; i < (int)y.size(); ++i) {
		int lst = -1, lv = -1;
		for (int j = l[i]; j <= r[i]; ++j) {
			if (h[j] < y[i]) {
				continue;
			}
			int v = ff++;
			ys[j].emplace_back(y[i], v);
			if (lst != -1) {
				edge(v, lv, abs(x[lst] - x[j]));
			}
			lst = j;
			lv = v;
		}
	}
	for (int i = 0; i < (int)x.size(); ++i) {
		ground[i] = ff++;
		sort(all(ys[i]));
		int ly = 0, lv = ground[i];
		for (auto cur : ys[i]) {
			edge(cur.y, lv, abs(cur.x - ly));
			tie(ly, lv) = cur;
		}
	}

	int from = ground[st], to = ground[fi];
	fill_n(dst, N, INF);
	dst[from] = 0;
	q.emplace(dst[from], from);
	while (q.size() && !istl()) {
		ll d, w;
		int v, u;
		tie(d, v) = q.top(); q.pop();
		if (d != dst[v]) {
			continue;
		}
		if (v == to) {
			break;
		}
		for (auto e : g[v]) {
			u = e.x, w = e.y;
			if (dst[u] > dst[v] + w) {
				dst[u] = dst[v] + w;
				q.emplace(dst[u], u);
			}
		}
	}
	if (dst[to] > INF / 2) {
		return -1;
	}
	return dst[to];
}

#ifdef LC
#include "grader.cpp"
#endif

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