Submission #281757

#	Time	Username	Problem	Language	Result	Execution time	Memory
281757		srvlt	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1094 ms	63656 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
#define cps(x) sort(all(x)), (x).erase(unique(all(x)), end(x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n0 = 30003;
int n, m, k;
vector <int> can[n0];
unordered_map <int, int> d;

int & get(int x, int y) {
	y++;
	return d[x * n0 + y];
}

void bfs(int sx, int sy) {
	deque <array <int, 2>> q;
	get(sx, sy) = 1;
	q.pb({sx, sy});
	while (!q.empty()) {
		auto p = q.front();
		q.pop_front();
		int & d1 = get(p[0], p[1]);
		if (p[1] != -1) {
			if (p[0] + p[1] < n) {
				int & d2 = get(p[0] + p[1], p[1]);
				if (!d2 || d2 > d1 + 1) {
					d2 = d1 + 1;
					q.pb({p[0] + p[1], p[1]});
				}
			}
			if (p[0] - p[1] >= 0) {
				int & d2 = get(p[0] - p[1], p[1]);
				if (!d2 || d2 > d1 + 1) {
					d2 = d1 + 1;
					q.pb({p[0] - p[1], p[1]});
				}
			}
			int & d2 = get(p[0], -1);
			if (!d2 || d2 > d1) {
				d2 = d1;
				q.push_front({p[0], -1});
			}
		}	else {
			for (int i : can[p[0]]) {
				int & d2 = get(p[0], i);
				if (!d2 || d2 > d1) {
					d2 = d1;
					q.push_front({p[0], i});
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	cin >> n >> m;
	int A, B;
	for (int i = 0; i < m; i++) {
		int b, p;
		cin >> b >> p;
		if (i == 0) A = b;
		if (i == 1) B = b;
		can[b].pb(p);
	}
	bfs(A, -1);
	int & res = get(B, -1);
	if (!res) cout << -1;
	else cout << res - 1;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:18:13: warning: 'B' may be used uninitialized in this function [-Wmaybe-uninitialized]
   18 |  return d[x * n0 + y];
      |           ~~^~~~
skyscraper.cpp:64:9: note: 'B' was declared here
   64 |  int A, B;
      |         ^
skyscraper.cpp:72:5: warning: 'A' may be used uninitialized in this function [-Wmaybe-uninitialized]
   72 |  bfs(A, -1);
      |  ~~~^~~~~~~

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