Submission #778528

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
778528	2023-07-10T11:43:37 Z	Elias	Sky Walking (IOI19_walk)	C++17	Compilation error	0 ms	0 KB

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 > int(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 > int(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

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++)
      |                  ~~^~~~~~~~~~
walk.cpp:67:21: error: expected ';' before 'break'
   67 |    if (H > int(h[i])
      |                     ^
      |                     ;
   68 |     break;
      |     ~~~~~            
walk.cpp:67:10: warning: value computed is not used [-Wunused-value]
   67 |    if (H > int(h[i])
      |        ~~^~~~~~~~~~~
walk.cpp:69:55: error: expected ')' before ';' token
   69 |    adj[{b, lasth}].push_back({abs(H - lasth), {b, H}});
      |                                                       ^
      |                                                       )
walk.cpp:67:7: note: to match this '('
   67 |    if (H > int(h[i])
      |       ^
walk.cpp:69:29: error: could not convert '(& adj.std::map<std::pair<long int, long int>, std::vector<std::pair<long int, std::pair<long int, long int> > > >::operator[](std::pair<long int, long int>(b, lasth)))->std::vector<std::pair<long int, std::pair<long int, long int> > >::push_back(std::pair<long int, std::pair<long int, long int> >(std::abs((H - lasth)), std::pair<long int, long int>(b, (* & H))))' from 'void' to 'bool'
   69 |    adj[{b, lasth}].push_back({abs(H - lasth), {b, H}});
      |    ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
      |                             |
      |                             void