Submission #953964

#	Time	Username	Problem	Language	Result	Execution time	Memory
953964		JooDdae	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	149 ms	81592 KiB

skyscraper

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

const ll INF = 1e18;

int n, m, s[30030], p[30030];
ll d[30030];
vector<array<int, 2>> v[30030];
set<int> st[30030], did[30030];
priority_queue<array<int, 2>> pq;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for(int i=0;i<m;i++) {
		cin >> s[i] >> p[i];
		st[s[i]].insert(p[i]);
	}
	for(int i=0;i<m;i++) {
		if(did[s[i]].count(p[i])) continue;
		did[s[i]].insert(p[i]);
		for(int j=1;;j++) {
			int x = s[i]-p[i]*j;
			if(x < 0) break;
			v[s[i]].push_back({x, j});
			if(st[x].count(p[i])) break;
		}
		for(int j=1;;j++) {
			int x = s[i]+p[i]*j;
			if(x >= n) break;
			v[s[i]].push_back({x, j});
			if(st[x].count(p[i])) break;
		}
	}
	fill(d, d+n, INF);
	d[s[0]] = 0, pq.push({0, s[0]});
	while(!pq.empty()) {
		auto [c, u] = pq.top(); pq.pop();
		if(-c > d[u]) continue;
		for(auto [x, y] : v[u]) if(y-c < d[x]) d[x] = y-c, pq.push({c-y, x});
	}
	cout << (d[s[1]] == INF ? -1 : d[s[1]]);
}

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