Submission #569021

#	Time	Username	Problem	Language	Result	Execution time	Memory
569021		Alan	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	22 / 100	20 ms	6000 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<ll> adj[30000];

struct node {
	ll u, di, vel;
};

int main() {
	unordered_map<ll, bool> vis;
	ll n, m, b, p, d0, d1;
	cin >> n >> m;
	for (ll i = 0; i < m; i++) {
		cin >> 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 (!vis[(u<<30)+vel] && u+vel >= 0 && u+vel < n) bfs.push({u+vel, di+1, vel}), vis[(u<<30)+vel] = true;
		for (auto& s : adj[u]) if (!vis[(u<<30)+s]) bfs.push({u+s, di+1, s}), vis[(u<<30)+s] = true;
	}
	cout << "-1\n";
	
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:26:3: warning: 'd1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   26 |   if (u == d1) {
      |   ^~
skyscraper.cpp:23:10: warning: 'd0' may be used uninitialized in this function [-Wmaybe-uninitialized]
   23 |  bfs.push({d0, 0, 0});
      |  ~~~~~~~~^~~~~~~~~~~~

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