Submission #778529

#	Time	Username	Problem	Language	Result	Execution time	Memory
778529		Elias	Sky Walking (IOI19_walk)	C++17	24 / 100	4051 ms	765592 KiB

walk

#ifndef _DEBUG
#include "walk.h"
#endif

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

#define int int64_t

struct Bridge
{
	int l, r, h;

	bool operator<(Bridge other)
	{
		return vector<int>{l, r, h} < vector<int>{other.l, other.r, other.h};
	}
};

long long min_distance(std::vector<signed> x, std::vector<signed> h, std::vector<signed> l, std::vector<signed> r, std::vector<signed> y, signed s, signed g)
{
	map<pair<int, int>, vector<pair<int, pair<int, int>>>> adj;

	vector<Bridge> bridges;
	for (int i = 0; i < l.size(); i++)
	{
		bridges.push_back({x[l[i]], x[r[i]], y[i]});
	}

	sort(bridges.begin(), bridges.end());
	reverse(bridges.begin(), bridges.end());

	set<pair<int, int>> active;
	set<pair<int, int>> active_by_h;

	map<int, int> last_at_height;

	int i = 0;
	for (int b : x)
	{
		while (active.size() && active.begin()->first < b)
		{
			active_by_h.erase({active.begin()->second, active.begin()->first});
			active.erase(active.begin());
		}
		for (auto [H, end] : active_by_h)
		{
			if (H > h[i])
				break;
			int last = last_at_height[H];
			adj[{b, H}].push_back({abs(last - b), {last, H}});
			adj[{last, H}].push_back({abs(last - b), {b, H}});
		}

		while (bridges.size() && bridges.back().l == b)
		{
			assert(bridges.back().h <= h[i]);
			active.insert({bridges.back().r, bridges.back().h});
			active_by_h.insert({bridges.back().h, bridges.back().r});
			bridges.pop_back();
		}

		int lasth = 0;

		for (auto [H, end] : active_by_h)
		{
			if (H > h[i])
				break;
			adj[{b, lasth}].push_back({abs(H - lasth), {b, H}});
			adj[{b, H}].push_back({abs(H - lasth), {b, lasth}});
			lasth = H;
			last_at_height[H] = b;
		}

		i++;
	}

	assert(bridges.size() == 0);

	priority_queue<tuple<int, int, int>> pq;
	pq.push(tuple<int, int, int>{0, x[s], 0});

	map<pair<int, int>, int> dist;

	while (pq.size())
	{
		auto [d, px, py] = pq.top();
		pq.pop();

		if (dist.count({px, py}))
			continue;

		dist[{px, py}] = -d;

		for (auto [plusd, c] : adj[{px, py}])
		{
			if (dist.count(c) == 0)
				pq.push(tuple<int, int, int>{d - plusd, c.first, c.second});
		}
	}
	if (dist.count({x[g], 0}) == 0)
		return -1;
	return dist[{x[g], 0}];
}

#ifdef _DEBUG

signed main()
{
	signed n, m;
	assert(2 == scanf("%d%d", &n, &m));
	vector<signed> x(n), h(n);
	for (signed i = 0; i < n; i++)
		assert(2 == scanf("%d%d", &x[i], &h[i]));
	vector<signed> l(m), r(m), y(m);
	for (signed i = 0; i < m; i++)
		assert(3 == scanf("%d%d%d", &l[i], &r[i], &y[i]));
	signed s, g;
	assert(2 == scanf("%d%d", &s, &g));
	fclose(stdin);

	long long result = min_distance(x, h, l, r, y, s, g);

	cerr << result << "\n";
	fclose(stdout);
	return 0;
}

#endif

Compilation message (stderr)

walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:25:20: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for (int i = 0; i < l.size(); i++)
      |                  ~~^~~~~~~~~~

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