Submission #1275755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275755		pasta	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	566 ms	3844 KiB

skyscraper

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

typedef pair<int, int> pii;
typedef long long ll;
#define pb push_back
#define F  first
#define S  second
#define all(x) 		(x).begin(),(x).end()
const int maxn = 1e6 + 10;
//const int maxs = 9;
const int inf = 1e9 + 10;
const int mod = 998244353;

int n, m, b[maxn], p[maxn], d[maxn];
vector<int> G[maxn];


signed main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> b[i] >> p[i];
		G[b[i]].pb(p[i]);
	}	
	
	for (int i = 0; i < n; i++) {
		d[i] = inf;
	}
	
	set<pii> se;
	d[b[1]] = 0;
	se.insert({0, b[1]});
	
	while (!se.empty()) {
		auto tmp = *se.begin();
		se.erase(tmp);
		auto [d_, v] = tmp;
		
		for (int k : G[v]) {
			int w;
			
			w = 1;
			for (int u = v - k; u >= 0; u -= k) {
				if (d[u] > d[v] + w) {
					se.erase({d[u], u});
					d[u] = d[v] + w;
					se.insert({d[u], u});
				}
				w++;
			}
			
			w = 1;
			for (int u = v + k; u < n; u += k) {
				if (d[u] > d[v] + w) {
					se.erase({d[u], u});
					d[u] = d[v] + w;
					se.insert({d[u], u});
				}
				w++;
			}
		}
	}
	
	if (d[b[2]] >= inf)
		d[b[2]] = -1;
	cout << d[b[2]] << '\n';
}

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