Submission #411404

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
411404	2021-05-25T08:25:54 Z	장태환(#7572)	Sky Walking (IOI19_walk)	C++17	Compilation error	0 ms	0 KB

walk

#include "walk.h"
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
vector<pair<int, int>>re;
vector<pair<int, int>>link[2000100];
pair<int, int>bef[200100];
multiset<pair<int,int>>se;
long long dist[2000100];
int vis[2000100];
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 s, int g)
{
	int N = x.size();
	int M = l.size();
	int i;
	int vc = 0;
	for (i = 0; i < N; i++)
	{
		re.push_back({ x[i],i });
	}
	for (i = 0; i < M; i++)
	{
		re.push_back({ x[l[i]],-i-1 });
		re.push_back({ x[r[i]] + 1,-i-M-1 });
	}
	sort(re.begin(), re.end());

	int curv = N;
	for (i = 0; i < re.size(); i++)
	{
		if (re[i].second >= 0)
		{
			int befh = 0;
			int befv = re[i].second;
			for (auto j = se.begin(); j != se.end(); j++)
			{
				if ((*j).first > h[re[i].second])
					break;
				int he = (*j).first;
				link[befv].push_back({ curv,he - befh });
				link[curv].push_back({ befv,he - befh });
				int ve = (*j).second;
				if (bef[ve].second)
				{
					link[bef[ve].second].push_back({ curv,re[i].first - bef[ve].first });
					link[curv].push_back({ bef[ve].second,re[i].first - bef[ve].first });
				}
				bef[ve] = { re[i].first,curv };
				befh = he;
				befv = curv;
				curv++;
			}
		}
		else if (re[i].second >=-M)
		{
			int te = -re[i].second - 1;
			se.insert({ y[te],te });
		}
		else
		{
			int te = -re[i].second - 1-M;
			se.erase({ y[te],te });
		}
	}
	memset(dist, 1, sizeof(dist));
	priority_queue<pair<int, int>>pq;
	pq.push({ 0,s });
	while (pq.size())
	{
		auto a = pq.top();
		pq.pop();
		if (vis[a.second])
			continue;
		vis[a.second] = 1;
		for (i = 0; i < link[a.second].size(); i++)
		{
			if (dist[link[a.second][i].first] > -a.first + link[a.second][i].second)
			{
				dist[link[a.second][i].first] = -a.first + link[a.second][i].second;
				pq.push({ -dist[link[a.second][i].first],link[a.second][i].first });
			}
		}
	}
	return (dist[g]>(1LL<<50))?-1:dist[g];
}

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:30:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for (i = 0; i < re.size(); i++)
      |              ~~^~~~~~~~~~~
walk.cpp:66:2: error: 'memset' was not declared in this scope
   66 |  memset(dist, 1, sizeof(dist));
      |  ^~~~~~
walk.cpp:5:1: note: 'memset' is defined in header '<cstring>'; did you forget to '#include <cstring>'?
    4 | #include <queue>
  +++ |+#include <cstring>
    5 | using namespace std;
walk.cpp:76:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for (i = 0; i < link[a.second].size(); i++)
      |               ~~^~~~~~~~~~~~~~~~~~~~~~~
walk.cpp:17:6: warning: unused variable 'vc' [-Wunused-variable]
   17 |  int vc = 0;
      |      ^~