Submission #958540

#	Time	Username	Problem	Language	Result	Execution time	Memory
958540		MinaRagy06	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	696 ms	9164 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 30'005, B = 1;
vector<int> gud[N];
int dist[N][B + 5][2], ok[N][B + 5];
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n, m;
	cin >> n >> m;
	int st = -1, en = -1;
	for (int i = 0; i < m; i++) {
		int b, p;
		cin >> b >> p;
		if (i == 0) st = b;
		if (i == 1) en = b;
		if (p < B) {
			ok[b][p] = 1;
		}
		gud[b].push_back(p);
	}
	memset(dist, '?', sizeof dist);
	priority_queue<array<int, 4>, vector<array<int, 4>>, greater<>> pq;
	pq.push({0, st, B, 0});
	dist[st][B][0] = 0;
	while (pq.size()) {
		int cost = pq.top()[0];
		int node = pq.top()[1];
		int pp = pq.top()[2];
		int ok2 = pq.top()[3];
		pq.pop();
		if (cost > dist[node][pp][ok2]) continue;
		if (pp < B) {
			int p = pp;
			if (p - 1 >= 0 && cost < dist[node][p - 1][0]) {
				dist[node][p - 1][0] = cost;
				pq.push({cost, node, p - 1, 0});
			}
			if (cost < dist[node][p + 1][0]) {
				dist[node][p + 1][0] = cost;
				pq.push({cost, node, p + 1, 0});
			}
			if (!ok[node][p] && !ok2) continue;
			if (node - p >= 0 && cost + 1 < dist[node - p][p][1]) {
				dist[node - p][p][1] = cost + 1;
				pq.push({cost + 1, node - p, p, 1});
			}
			if (node + p < n && cost + 1 < dist[node + p][p][1]) {
				dist[node + p][p][1] = cost + 1;
				pq.push({cost + 1, node + p, p, 1});
			}
		} else {
			if (cost < dist[node][pp - 1][0]) {
				dist[node][pp - 1][0] = cost;
				pq.push({cost, node, pp - 1, 0});
			}
			for (auto p : gud[node]) {
				if (p < B) continue;
				int cnt = 0;
				for (int nxt = node + p; nxt < n; nxt += p) {
					cnt++;
					if (cost + cnt < dist[nxt][B][0]) {
						dist[nxt][B][0] = cost + cnt;
						pq.push({cost + cnt, nxt, B, 0});
					}
				}
				cnt = 0;
				for (int nxt = node - p; nxt >= 0; nxt -= p) {
					cnt++;
					if (cost + cnt < dist[nxt][B][0]) {
						dist[nxt][B][0] = cost + cnt;
						pq.push({cost + cnt, nxt, B, 0});
					}
				}
			}
		}
	}
	cout << (dist[en][B][0] >= (ll) 1e9? -1 : dist[en][B][0]) << '\n';
	return 0;
}

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