Submission #380452

#	Time	Username	Problem	Language	Result	Execution time	Memory
380452		LittlePants	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	736 ms	112572 KiB

skyscraper

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

const int maxN = 30005;

int N, M, S, T;
std::vector<int> Doge[maxN];
std::queue<std::tuple<int, int, int>> Q;
std::bitset<maxN> vis[maxN];
bool Vis[maxN];

void insert(int i, int p, int step)
{
	if (!Vis[i])
	{
		Vis[i] = true;
		for (auto x : Doge[i])
			if (!vis[i].test(x))
				vis[i].set(x), Q.emplace(i, x, step);
	}
	if (!vis[i].test(p))
		vis[i].set(p), Q.emplace(i, p, step);
}

int main()
{
	scanf("%d%d", &N, &M);
	for (int i = 0, b, p; i != M; ++i)
	{
		scanf("%d%d", &b, &p);
		if (i == 0)
			S = b;
		if (i == 1)
			T = b;
		Doge[b].push_back(p);
	}

	if (S == T)
	{
		puts("0");
		return 0;
	}

	Vis[S] = true;
	for (auto x : Doge[S])
		if (!vis[S].test(x))
		{
			vis[S].set(x);
			Q.emplace(S, x, 0);
		}

	while (!Q.empty())
	{
		int i, p, step;
		std::tie(i, p, step) = Q.front();
		Q.pop();
		if (i - p == T || i + p == T)
		{
			printf("%d\n", step + 1);
			return 0;
		}
		if (i - p >= 0)
			insert(i - p, p, step + 1);
		if (i + p < N)
			insert(i + p, p, step + 1);
	}

	puts("-1");

	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |   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