Submission #1210315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210315		k1r1t0	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	1004 ms	24904 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

const int N = 31000;
const int S = 174;
const int INF = (int)(1e9);

int dist[N][S], n, m;
vector<int> p[N];

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	int pos1, pos2;
	for (int i = 1; i <= m; i++) {
		int x, y; cin >> x >> y;
		x++;
		p[x].push_back(y);
		if (i == 1) pos1 = x;
		if (i == 2) pos2 = x;
	}
	for (int i = 1; i <= n; i++)
	for (int j = 0; j < S; j++)
		dist[i][j] = INF;
	dist[pos1][0] = 0;
	set<array<int, 3>> qq;
	qq.insert({0, pos1, 0});
	while (!qq.empty()) {
		auto [d, u, v] = *qq.begin(); qq.erase(qq.begin());
		vector<array<int, 3>> gg;
		if (v == 0) {
			set<int> st;
			for (int j : p[u])
				st.insert(j);
			for (int j : st)
				if (j >= S) {
					for (int k = u + j; k <= n; k += j)
						gg.push_back({(k - u) / j, k, 0});
					for (int k = u - j; k >= 1; k -= j)
						gg.push_back({(u - k) / j, k, 0});
				} else
					gg.push_back({0, u, j});
		} else {
			gg.push_back({0, u, 0});
			if (u - v >= 1)
				gg.push_back({1, u - v, v});
			if (u + v <= n)
				gg.push_back({1, u + v, v});
		}
		for (auto [w, x, y] : gg)
			if (d + w < dist[x][y]) {
				qq.erase({dist[x][y], x, y});
				dist[x][y] = d + w;
				qq.insert({dist[x][y], x, y});
			}
	}
	int ans = dist[pos2][0];
	if (ans == INF) ans = -1;
	cout << ans;
}

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