Submission #1164280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164280		pacman	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	1 ms	1168 KiB

skyscraper

#include <bits/stdc++.h>
#define ll long long int
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define plli pair<long long int , long long int>
#define pcc pair<char,char>
#define pbb pair<bool,bool>
#define PB push_back
#define PF push_front
#define MOD 1000000007
#define intxt freopen("input.txt","r",stdin)
#define outtxt freopen("output.txt","w",stdout)

using namespace std;

const int MAXN = 3e4 + 10;
const ll inf = 1e17;
ll n ,m ,q1 ,q2 ,h[MAXN];
vector <pii> adj[MAXN];
set <pii> p;

inline void dijkstra(ll x) {
	for(int i = 0 ; i <= n ; i++) {
		h[i] = inf;
		if(i == x) {
			h[i] = 0;
		}
		p.insert({h[i] , i});
	}
	
	while(p.size()) {
		ll v = (*p.begin()).s;
		p.erase(*p.begin());
		for(auto [u , w] : adj[v]) {
			if(h[u] > h[v] + w) {
				p.erase({h[u] , u});
				h[u] = h[v] + w;
				p.insert({h[u] , u});
			}
		}
	}
}

int main() {
	
	ios_base::sync_with_stdio(0);
	
	cin >> n >> m;
	
	ll s ,e;
	for(int i = 1 ; i <= m ; i++) {
		cin >> q1 >> q2;
		if(i == 1) {
			s = q1;
		}
		if(i == 2) {
			e = q2;
		}
		for(int i = 1 ; q1 + (i * q2) <= n ; i++) {
			adj[q1].PB({q1 + (i * q2) , i});
		}
		for(int i = 1 ; q1 - (i * q2) >= 0 ; i++) {
			adj[q1].PB({q1 - (i * q2) , i});
		}
	}
	
	dijkstra(s);
	
	cout << h[e];
	
}
//Hello

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