Submission #281753

#	Time	Username	Problem	Language	Result	Execution time	Memory
281753		srvlt	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1036 ms	31736 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];
map <array <int, 2>, int> d;

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

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:69:24: warning: 'B' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |  else cout << d[{B, -1}] - 1;
      |                        ^
skyscraper.cpp:67:5: warning: 'A' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |  bfs(A, -1);
      |  ~~~^~~~~~~

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