Submission #1130957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130957		am_aadvik	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	929 ms	22768 KiB

skyscraper

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma unroll
#include <iostream>
#include<vector>
#include<math.h>
#include<set>
const int inf = 1e9;
const int mxn = 3e4 + 5;
using namespace std;
vector<int> g[mxn];
set<vector<int>> q; //{dist, pos, power}
vector<vector<int>> dist;

void vis(int i, int p, int c) {
	if (dist[p][i] > c) {
		if (dist[p][i] != inf) q.erase({ dist[p][i], i, p });
		dist[p][i] = c;
		q.insert({ c, i, p });
	}

}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int n, m, s = -1, sq, t = -1; cin >> n >> m;
	sq = 150;

	for (int i = 0; i < m; ++i) {
		int x, y; cin >> x >> y;
		if (i == 0) s = x;
		if (i == 1) t = x;
		g[x].push_back(y);
	}

	dist.assign(sq, vector<int>(n, inf));
	q.insert({ 0, s, 0 });
	dist[0][s] = 0;

	while (!q.empty()) {
		auto f = *q.begin(); q.erase(q.begin());
		if (f[1] == t) { cout << f[0]; return 0; }

		if (f[2] == 0) {
			for (auto x : g[f[1]]) {
				if (x < sq)
					vis(f[1], x, f[0]);
				else {
					if (f[1] >= x)
						for (int i = f[1] - x, v = 1; i >= 0; i -= x, ++v)
							vis(i, 0, v + f[0]);
					if ((f[1] + x) < n)
						for (int i = f[1] + x, v = 1; i < n; i += x, ++v)
							vis(i, 0, v + f[0]);
				}
			}
		}
		else {
			vis(f[1], 0, f[0]);
			if (f[1] >= f[2])
				vis(f[1] - f[2], f[2], f[0] + 1);
			if ((f[1] + f[2]) < n)
				vis(f[1] + f[2], f[2], f[0] + 1);
		}
	}
	cout << -1;
}

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