Submission #315867

#	Time	Username	Problem	Language	Result	Execution time	Memory
315867		parsabahrami	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	948 ms	7160 KiB

skyscraper

//! Starman - Dawid Bowie
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;
 
#define sz(x)                       (ll) x.size()
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second

ll Pow(ll a, ll b, ll md, ll ans = 1) {
    for (; b; b >>= 1, a = a * a % md)
        if (b & 1)
            ans = ans * a % md;
    return ans % md;
}
const ll MAXN = 5e4 + 10;
const ll INF  = 1e18;
const ll MOD  = 1e9 + 7;
priority_queue<pll> pq; vector<ll> vec[MAXN];
ll mark[MAXN], dist[MAXN], B[MAXN], P[MAXN], st, en, n, m;

int main() {
	scanf("%lld%lld", &n, &m);
	for (ll i = 0; i < m; i++) {
		scanf("%lld%lld", &B[i], &P[i]);
		if (i == 0) st = B[i];
		if (i == 1) en = B[i];
		vec[B[i]].push_back(P[i]);
	}
	fill(dist, dist + MAXN, INF);
	pq.push({dist[st] = 0, st});
	while (sz(pq)) {
		ll v = pq.top().S; pq.pop();
		if (mark[v]) continue;
		mark[v] = 1;
		for (ll u : vec[v]) {
			for (ll i = 0, j = v; j >= 0; j -= u, i++) {
				if (dist[j] > dist[v] + i) {
					dist[j] = dist[v] + i;
					pq.push({-dist[j], j});
				}
			}
			for (ll i = 0, j = v; j < n; j += u, i++) {
				if (dist[j] > dist[v] + i) {
					dist[j] = dist[v] + i;
					pq.push({-dist[j], j});
				}
			}
		}
	}
	if (dist[en] == INF) return !printf("-1\n");
	else printf("%lld\n", dist[en]);
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |  scanf("%lld%lld", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |   scanf("%lld%lld", &B[i], &P[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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