Submission #1127365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127365		daoquanglinh2007	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	36 / 100	69 ms	700 KiB

skyscraper

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

#define int long long
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair

const int NM = 30000, MM = 2000, inf = 1e18;

int N, M, B[MM+5], P[MM+5];
int d[MM+5];
priority_queue <pii, vector <pii>, greater <pii> > pq;

void dijkstra(){
	for (int i = 0; i < M; i++) d[i] = +inf;
	d[0] = 0;
	while (!pq.empty()) pq.pop();
	pq.push(mp(0, 0));
	
	while (!pq.empty()){
		int u = pq.top().se;
		if (d[u] != pq.top().fi){
			pq.pop();
			continue;
		}
		pq.pop();
		for (int v = 0; v < M; v++){
			if ((B[u]-B[v])%P[u] != 0) continue;
			int w = abs(B[u]-B[v])/P[u];
			if (d[u]+w < d[v]){
				d[v] = d[u]+w;
				pq.push(mp(d[v], v));
			}
		}
	}
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N >> M;
	for (int i = 0; i < M; i++)
		cin >> B[i] >> P[i];
	dijkstra();
	if (d[1] == +inf) cout << -1;
	else cout << d[1];
	return 0;
}

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