oj.uz

Submission #778511

# Submission time Handle Problem Language Result Execution time Memory
778511 2023-07-10T11:32:03 Z Elias Sky Walking (IOI19_walk) C++17
0 / 100
 4000 ms 726372 KB 
#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>, int> dist;
	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)
		{
			last_at_height[bridges.back().h] = b;
			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++;
	}

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

	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});
		}
	}
	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:26: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]
   26 |  for (int i = 0; i < l.size(); i++)
      |                  ~~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2101 ms 190404 KB Output is correct
4 Correct 1501 ms 207484 KB Output is correct
5 Correct 655 ms 136180 KB Output is correct
6 Correct 610 ms 120828 KB Output is correct
7 Incorrect 712 ms 136196 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 24020 KB Output is correct
2 Execution timed out 4091 ms 726372 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 24020 KB Output is correct
2 Execution timed out 4091 ms 726372 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -