Submission #1242807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242807		Boas	Sky Walking (IOI19_walk)	C++20	24 / 100	2709 ms	1114112 KiB

walk

#include "walk.h"

// #pragma GCC optimize("trapv")

#include <bits/stdc++.h>
using namespace std;

#define int long long

#define loop(n, i) for (int i = 0; i < n; i++)
#define pb push_back
#define sz(x) (int)(x).size()

typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<int32_t> vi32;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef set<ii> sii;
typedef map<int, int> mii;

int INF = 1e18;

int min_distance(vi32 x, vi32 h, vi32 l, vi32 r, vi32 y, int32_t s, int32_t g)
{
	int n = sz(x), m = sz(l);
	vector<map<int, vi>> adj(n);
	vvi endsHere(n), startHere(n);
	loop(m, i) endsHere[r[i]].pb(i);
	loop(m, i) startHere[l[i]].pb(i);
	vvi intersects(m);
	sii active; // {y, ix}
	loop(n, i)
	{
		for (int j : startHere[i])
			active.insert({y[j], j});
		for (auto it = begin(active); it != end(active); it++)
		{
			if (it->first > h[i])
				break;
			intersects[it->second].pb(i);
		}
		for (int j : endsHere[i])
			active.erase({y[j], j});
	}
	loop(m, i)
	{
		for (int p : intersects[i])
		{
			for (int p2 : intersects[i])
			{
				if (p == p2)
					continue;
				adj[p][y[i]].pb(p2);
			}
		}
	}
	priority_queue<iii, vector<iii>, greater<iii>> q;
	vector<mii> disList(n);
	auto dis = [&](int p, int y) -> int
	{
		if (disList[p].count(y))
			return disList[p][y];
		return INF;
	};
	q.push({0, s, 0});
	while (!q.empty())
	{
		auto [d, p, y] = q.top();
		q.pop();
		if (dis(p, y) < d)
			continue;
		disList[p][y] = d;
		for (int p2 : adj[p][y])
		{
			int d2 = d + abs(x[p2] - x[p]);
			if (d2 < dis(p2, y))
			{
				disList[p2][y] = d2;
				q.push({d2, p2, y});
			}
		}
		auto nxt = adj[p].upper_bound(y);
		if (nxt != adj[p].end())
		{
			int y2 = nxt->first;
			int d2 = d + abs(y2 - y);
			if (d2 < dis(p, y2))
			{
				disList[p][y2] = d2;
				q.push({d2, p, y2});
			}
		}
		if (prev(nxt) != adj[p].begin())
		{
			nxt = prev(prev(nxt));
			int y2 = nxt->first;
			int d2 = d + abs(y2 - y);
			if (d2 < dis(p, y2))
			{
				disList[p][y2] = d2;
				q.push({d2, p, y2});
			}
		}
	}
	int res = INF;
	for (auto [y, adjY] : adj[g])
	{
		res = min(res, dis(g, y) + y);
	}
	if (res == INF)
		return -1;
	return res;
}

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