Submission #569198

#	Time	Username	Problem	Language	Result	Execution time	Memory
569198		Alan	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	264 ms	112292 KiB

skyscraper

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
 
vector<int> adj[30001];
 
struct node {
	int u, di, vel;
};
 
int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(0);
	bitset<30001> vis[30001];
	int n, m, b, p, d0 = 0, d1 = 0;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		scanf("%d %d", &b, &p);
		if (i == 0) d0 = b;
		if (i == 1) d1 = b;
		if (0 <= b+p && b+p < n) adj[b].push_back(p);
		if (0 <= b-p && b-p < n) adj[b].push_back(-p);
	}

	queue<node> bfs;
	bfs.push({d0, 0, 0});
	while (!bfs.empty()) {
		auto [u, di, vel] = bfs.front();
		if (u == d1) {
			cout << di << "\n";
			return 0;
		}
		bfs.pop();
		if (u+vel >= 0 && u+vel < n && vel && !vis[u][u+vel]) bfs.push({u+vel, di+1, vel}), vis[u].set(u+vel);
		for (auto& s : adj[u]) if (s && !vis[u][u+s]) bfs.push({u+s, di+1, s}), vis[u].set(u+s);
	}
	cout << "-1\n";
	
	return 0;
}

Compilation message (stderr)

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