Submission #1026810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026810		fv3	Sky Walking (IOI19_walk)	C++14	10 / 100	4064 ms	1048576 KiB

walk

/*
Sky Walking
*/
#include <bits/stdc++.h>
#include "walk.h"

using namespace std;
typedef long long ll;
const ll INF = 1ll << 60ll;

struct node
{
	ll x, y; 
	ll index;
	vector<pair<int, ll>> adj;
};

struct walk
{
	int l, r, y;
	bool operator<(const walk other) const
	{
		return y < other.y;
	}
};

ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int S, int G) 
{
	const int N = X.size();
	const int M = L.size();

	vector<walk> walks(M);
	for (int i = 0; i < M; i++)
		walks[i] = {L[i], R[i], Y[i]};
	sort(walks.begin(), walks.end());

	// Construct adjacency list
	vector<node> nodes;
	vector<int> top(N);
	for (int i = 0; i < N; i++)
	{
		nodes.push_back({X[i], 0, i, {}});
		top[i] = i; 
	}

	for (auto w : walks)
	{
		int last = -1;
		for (int i = w.l; i <= w.r; i++)
		{
			if (H[i] < w.y) continue;

			int index = nodes.size();
			node newNode = {X[i], w.y, index, {}};

			ll vdist = w.y - nodes[top[i]].y;

			nodes[top[i]].adj.push_back({index, vdist});
			newNode.adj.push_back({top[i], vdist});
			top[i] = index;

			if (last != -1)
			{
				ll hdist = X[i] - nodes[last].x;

				newNode.adj.push_back({last, hdist});
				nodes[last].adj.push_back({index, hdist});
			}
			last = index;

			nodes.push_back(newNode);
		}
	}

	priority_queue<pair<ll, int>> q;
	q.push({0ll, S});

	ll sz = nodes.size();

	vector<int> visited(sz);
	vector<ll> dist(sz, INF);
	dist[S] = 0;

	while (!q.empty())
	{
		int s = q.top().second;
		q.pop();

		if (visited[s]) continue;
		visited[s] = 1;

		for (auto n : nodes[s].adj)
		{
			if (visited[n.first]) continue;
			if (dist[s] + n.second < dist[n.first])
			{
				dist[n.first] = dist[s] + n.second;
				q.push({-dist[n.first], n.first});
			}
		}
	}

	if (dist[G] == INF)
		return -1;
	return dist[G];
}

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