Submission #414426

#	Time	Username	Problem	Language	Result	Execution time	Memory
414426		grt	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	862 ms	52936 KiB

skyscraper

#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back

using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 30 * 1000 + 10, B = 150, INF = 1e9 + 10;
int n, m;
int jump[nax], pos[nax];
vector<pi>V[nax];
bool exists[nax][B + 10];
int dist[nax][B + 10];
priority_queue<pair<int, pi>>PQ;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j <= B; ++j) {
			dist[i][j] = INF;
		}
	}
	for(int i = 1; i <= m; ++i) {
		cin >> pos[i] >> jump[i];
		if(jump[i] > B) {
			for(int j = 1; j * jump[i] + pos[i] < n; ++j) {
				V[pos[i]].emplace_back(j * jump[i] + pos[i], j);
			}
			for(int j = -1; j * jump[i] + pos[i] >= 0; --j) {
				V[pos[i]].emplace_back(j * jump[i] + pos[i], -j);
			}
		} else {
			exists[pos[i]][jump[i]] = true;
		}
	}
	dist[pos[1]][jump[1]] = 0;
	PQ.push({0, {pos[1], jump[1]}});
	while(!PQ.empty()) {
		auto [x, y] = PQ.top();
		PQ.pop();
		if(-x > dist[y.ST][y.ND]) continue;
		if(y.ST == pos[2]) {
			cout << -x;
			return 0;
		}
		if(y.ND == 0) {
			for(auto nbh : V[y.ST]) {
				if(dist[nbh.ST][0] > -x + nbh.ND) {
					dist[nbh.ST][0] = -x + nbh.ND;
					PQ.push({-dist[nbh.ST][0], {nbh.ST, 0}});
				}
			}
			for(int i = 1; i <= B; ++i) {
				if(exists[y.ST][i] && dist[y.ST][i] > -x) {
					dist[y.ST][i] = -x;
					PQ.push({-dist[y.ST][i], {y.ST, i}});
				}
			}
		} else {
			if(dist[y.ST][0] > -x) {
				dist[y.ST][0] = -x;
				PQ.push({x, {y.ST, 0}});
			}
			for(int d : {-y.ND, y.ND}) {
				if(y.ST + d < n && y.ST + d >= 0) {
					if(dist[y.ST + d][y.ND] > -x + 1) {
						dist[y.ST + d][y.ND] = -x + 1;
						PQ.push({-(-x + 1), {y.ST + d, y.ND}});
					}
				}
			}
		}
	}
	cout << "-1";
}

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