Submission #569039

#	Time	Username	Problem	Language	Result	Execution time	Memory
569039		Alan	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	22 / 100	8 ms	3412 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() {
	using h = hash<int>;
	auto hash = [] (const pair<int, int> a) {
		int res = 17;
		res = res*31 + h() (a.first);
		return res*31 + h() (a.second);
	};
	unordered_map<pair<int, int>, bool, decltype(hash)> vis (8, hash);
	ll n, m, b, p, d0, d1;
	cin >> n >> m;
	for (int 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, vel}] && u+vel >= 0 && u+vel < n) bfs.push({u+vel, di+1, vel}), vis[{u, vel}] = true;
		for (auto& s : adj[u]) if (!vis[{u, s}]) bfs.push({u+s, di+1, s}), vis[{u, s}] = true;
	}
	cout << "-1\n";
	
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:32:3: warning: 'd1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   32 |   if (u == d1) {
      |   ^~
skyscraper.cpp:29:10: warning: 'd0' may be used uninitialized in this function [-Wmaybe-uninitialized]
   29 |  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