Submission #322139

#	Time	Username	Problem	Language	Result	Execution time	Memory
322139		arnold518	Sky Walking (IOI19_walk)	C++14	10 / 100	4080 ms	163804 KiB

walk

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const ll INF = 1e15;

struct Build
{
	int X, H;
};

struct Line
{
	int L, R, Y;
};

int N, M, S, E;
Build A[MAXN+10];
Line B[MAXN+10];
vector<int> V[MAXN+10];
vector<ll> dist[MAXN+10];
vector<pii> L[MAXN+10], R[MAXN+10];

struct Queue
{
	int x, y; ll w;
	bool operator < (const Queue &p) const
	{
		return w>p.w;
	}
};

ll min_distance(vector<int> _X, vector<int> _H, vector<int> _L, vector<int> _R, vector<int> _Y, int _S, int _E)
{
	N=_X.size(); M=_L.size();
	for(int i=0; i<N; i++) A[i+1]={_X[i], _H[i]};
	for(int i=0; i<M; i++) B[i+1]={_L[i]+1, _R[i]+1, _Y[i]};
	S=_S+1; E=_E+1;

	for(int i=1; i<=N; i++) V[i].push_back(0);
	for(int i=1; i<=M; i++)
	{
		for(int j=B[i].L; j<=B[i].R; j++)
		{
			if(B[i].Y<=A[j].H)
			{
				V[j].push_back(B[i].Y);
			}
		}
	}

	for(int i=1; i<=N; i++)
	{
		sort(V[i].begin(), V[i].end());
		dist[i]=vector<ll>(V[i].size(), INF);
		L[i]=vector<pii>(V[i].size(), pii(0, 0));
		R[i]=vector<pii>(V[i].size(), pii(N+1, 0));
	}

	for(int i=1; i<=M; i++)
	{
		int by=lower_bound(V[B[i].L].begin(), V[B[i].L].end(), B[i].Y)-V[B[i].L].begin(), bx=B[i].L;
		for(int j=B[i].L+1; j<=B[i].R; j++)
		{
			if(B[i].Y<=A[j].H)
			{
				int y=lower_bound(V[j].begin(), V[j].end(), B[i].Y)-V[j].begin(), x=j;
				L[x][y]=pii(bx, by);
				R[bx][by]=pii(x, y);
				by=y; bx=x;
			}
		}
	}

	priority_queue<Queue> PQ;
	PQ.push({S, 0, 0});
	while(!PQ.empty())
	{
		Queue now=PQ.top(); PQ.pop();
		if(dist[now.x][now.y]<=now.w) continue;
		dist[now.x][now.y]=now.w;

		if(now.y+1<V[now.x].size()) PQ.push({now.x, now.y+1, now.w+V[now.x][now.y+1]-V[now.x][now.y]});
		if(now.y-1>=0) PQ.push({now.x, now.y-1, now.w+V[now.x][now.y]-V[now.x][now.y-1]});
		if(L[now.x][now.y].first>=1) PQ.push({L[now.x][now.y].first, L[now.x][now.y].second, now.w+A[now.x].X-A[L[now.x][now.y].first].X});
		if(R[now.x][now.y].first<=N) PQ.push({R[now.x][now.y].first, R[now.x][now.y].second, now.w-A[now.x].X+A[R[now.x][now.y].first].X});
	}
	if(dist[E][0]==INF) return -1;
	return dist[E][0];
}

Compilation message (stderr)

walk.cpp: In function 'll min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:88:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   if(now.y+1<V[now.x].size()) PQ.push({now.x, now.y+1, now.w+V[now.x][now.y+1]-V[now.x][now.y]});
      |      ~~~~~~~^~~~~~~~~~~~~~~~

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