Submission #229546

#	Time	Username	Problem	Language	Result	Execution time	Memory
229546		frodakcin	Jakarta Skyscrapers (APIO15_skyscraper)	C++11	100 / 100	101 ms	2304 KiB

skyscraper

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

const int MN = 3e4 + 10;
int N, M, st, end;
std::vector<int> a[MN];
struct state {public: int b, p, d, j;};
std::queue<state> q;
bool u[MN];

int main(void)
{
	scanf("%d%d", &N, &M);
	for(int i=0,b,p;i<M;++i)
	{
		scanf("%d%d", &b, &p);
		if(i == 0) st = b;
		if(i==1) end = b;
		else a[b].push_back(p);
	}
	if(st == end)
		return printf("0\n"), 0;
	for(int i=0;i<N;++i)
		std::sort(a[i].begin(), a[i].end()), a[i].resize(std::distance(a[i].begin(), std::unique(a[i].begin(), a[i].end())));
	for(int x : a[st])
	{
		if(st >= x) q.push({st-x, x, 1, -1});
		if(st+x<N) q.push({st+x, x, 1, 1});
	}
	u[st] = 1;
	for(;!q.empty();q.pop())
	{
		state n = q.front();
		if(n.b == end)
			return printf("%d\n", n.d), 0;
		if(!u[n.b])
		{
			u[n.b] = 1;
			for(int x : a[n.b])
			{
				if(x == n.p) continue;
				if(n.b >= x) q.push({n.b-x, x, n.d+1, -1});
				if(n.b+x<N) q.push({n.b+x, x, n.d+1, 1});
			}
		}
		else
		{
			std::vector<int>::iterator it = std::lower_bound(a[n.b].begin(), a[n.b].end(), n.p);
			if(it != a[n.b].end() && *it == n.p) continue;
		}
		int nx = n.b + n.p*n.j;
		if(0 <= nx && nx < N)
			q.push({nx, n.p, n.d+1, n.j});
	}
	printf("-1\n");
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &b, &p);
   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 43 / 43