Submission #427770

#	Time	Username	Problem	Language	Result	Execution time	Memory
427770		albertolg101	Sky Walking (IOI19_walk)	C++17	10 / 100	4086 ms	527088 KiB

walk

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

using namespace std; 
using ll = long long;
using pii = pair<int, int>;

const ll INFLL = 1e18;

long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> L, std::vector<int> R, std::vector<int> y, int start, int end) {

	int n = x.size(), 
		m = y.size();

	vector<pii> cc;
	vector<vector<int>> skywalk(n);
	cc.push_back({start, 0});
	cc.push_back({end, 0});
	skywalk[start].push_back(0);
	skywalk[end].push_back(0);

	for(int i = 0 ; i < m ; i++)
	{
		for(int j = L[i] ; j <= R[i] ; j++)
		{
			if(h[j] >= y[i])
			{
				cc.push_back({j, y[i]});
				skywalk[j].push_back(y[i]);
			}
		}
	}

	sort(cc.begin(), cc.end());
	cc.resize(unique(cc.begin(), cc.end()) - cc.begin());
	
	vector<vector<pair<int, ll>>> g(cc.size());

	for(int i = 0 ; i < n ; i++)
	{
		sort(skywalk[i].begin(), skywalk[i].end());

		for(int j = 0 ; j + 1 < skywalk[i].size() ; j++)
		{
			int a = lower_bound(cc.begin(), cc.end(), (pii){i, skywalk[i][j]}) - cc.begin(), 
				b = lower_bound(cc.begin(), cc.end(), (pii){i, skywalk[i][j+1]}) - cc.begin();
			ll w = skywalk[i][j+1] - skywalk[i][j];

			g[a].push_back({b, w});
			g[b].push_back({a, w});
		}
	}

	for(int i = 0 ; i < m ; i++)
	{
		int a = -1;
		for(int j = L[i] ; j <= R[i] ; j++)
		{
			if(h[j] >= y[i])
			{
				if(a == -1)
				{
					a = lower_bound(cc.begin(), cc.end(), (pii){j, y[i]}) - cc.begin();
				}

				else
				{
					int b = lower_bound(cc.begin(), cc.end(), (pii){j, y[i]}) - cc.begin(); 
					ll w = x[cc[b].first] - x[cc[a].first];

					g[a].push_back({b, w});
					g[b].push_back({a, w});

					a = b;
				}
			}
		}
	}

	priority_queue<pair<ll, int>> q;
	int s = lower_bound(cc.begin(), cc.end(), (pii){start, 0}) - cc.begin();
	q.push({0, s});

	vector<bool> flag(cc.size());
	vector<ll> dp(cc.size(), INFLL);
	dp[s] = 0;

	while(q.size())
	{
		int nod = q.top().second;
		q.pop();

		if(flag[nod])
			continue;

		flag[nod] = true;

		for(auto i: g[nod])
		{
			if(dp[i.first] > dp[nod] + i.second)
			{
				dp[i.first] = dp[nod] + i.second;
				q.push({-dp[i.first], i.first});
			}
		}
	}

	int e = lower_bound(cc.begin(), cc.end(), (pii){end, 0}) - cc.begin();
	return (dp[e] == INFLL ? -1 : dp[e]);
}

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:43:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for(int j = 0 ; j + 1 < skywalk[i].size() ; j++)
      |                   ~~~~~~^~~~~~~~~~~~~~~~~~~

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