Submission #417257

#	Time	Username	Problem	Language	Result	Execution time	Memory
417257		Mlxa	Sky Walking (IOI19_walk)	C++14	10 / 100	2651 ms	437808 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 = 1e6 + 10;
map<pair<int, int>, int> was;

int id(int x, int y) {
	auto p = mp(x, y);
	if (was.count(p)) {
		return was[p];
	} else {
		int v = (int)was.size();
		assert(v < N);
		return was[p] = v;
	}
}

vector<pair<int, int>> g[N];
set<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];
}

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 = l[i];
		for (int j = l[i] + 1; j <= r[i]; ++j) {
			if (h[j] < y[i]) {
				continue;
			}
			edge(id(x[lst], y[i]), id(x[j], y[i]), abs(x[lst] - x[j]));
			lst = j;
		}
		for (int j = l[i]; j <= r[i]; ++j) {
			if (h[j] >= y[i]) {
				ys[j].insert(y[i]);
			}
		}
	}
	for (int i = 0; i < (int)x.size(); ++i) {
		int ly = 0, lv = id(x[i], 0);
		for (int cur : ys[i]) {
			int ver = id(x[i], cur);
			edge(lv, ver, abs(cur - ly));
			ly = cur, lv = ver;
		}
	}

	int from = id(x[st], 0), to = id(x[fi], 0);
	fill_n(dst, N, INF);
	dst[from] = 0;
	q.emplace(dst[from], from);
	while (q.size()) {
		ll d, w;
		int v, u;
		tie(d, v) = q.top(); q.pop();
		if (d != dst[v]) {
			continue;
		}
		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