Submission #1138046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138046		Tsagana	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	22 ms	4544 KiB

skyscraper

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

void solve () {
	int n, m; cin >> n >> m;

	int tx;
	vector<int> dis(n, INT_MAX);
	vector<set<int>> p(n);
	pq<pair<int, int>> q;

	for (int i = 0; i < m; i++) {
		int x, y; cin >> x >> y;

		p[x].insert(y);

		if (!i) {dis[x] = 0; q.push({0, x});}
		if (i == 1) tx = x;
	}

	while (!q.empty()) {
		auto [d, x] = q.top(); d = -d; q.pop();
		if (d != dis[x]) continue;

		for (auto j : p[x]) {
			for (int i = x + j; i < n; i += j) {
				if (!p[i].empty() && d + abs(x - i) / j < dis[i]) {
					dis[i] = d + abs(i - x) / j;
					q.push({-dis[i], i});
				}
				if (p[i].find(j) != p[i].end()) break;
			}
			for (int i = x - j; i >= 0; i -= j) {
				if (!p[i].empty() && d + abs(i - x) / j < dis[i]) {
					dis[i] = d + abs(i - x) / j;
					q.push({-dis[i], i});
				}
				if (p[i].find(j) != p[i].end()) break;
			}
		}
	}
	cout << (dis[tx] == INT_MAX ? -1 : dis[tx]);
}
signed main() {IOS solve(); return 0;}

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