Submission #566950

#	Time	Username	Problem	Language	Result	Execution time	Memory
566950		Sharky	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	770 ms	7928 KiB

skyscraper

// trying c8kism be like
#include <bits/stdc++.h>
#define ef else if
#define pb push_back
#define leave exit(0);

using namespace std;

typedef int _;
typedef pair<_, _> _p;
typedef vector<_> v_;
typedef const long long constant;
constant maxn = 3E4 + 5;

_ n, m, c, b[maxn], p[maxn], dist[maxn];
set<_> dg[maxn];
void dijk(_ s);
int main() {

    scanf("%d %d", &n, &m);
    for (_ i = 0; i < m; ++i) scanf("%d %d", &b[i], &p[i]), dg[b[i]].insert(p[i]);
    if (b[0] == b[1]) puts("0"), leave
    dijk(b[0]);
    if (dist[b[1]] == 1E9) cout << "-1\n";
    else cout << dist[b[1]] << "\n";
    
    return 0;
}

void dijk(_ s) {
    priority_queue<_p, vector<_p>, greater<_p> > q;
    fill(dist, dist + maxn, 1E9);
    dist[s] = 0;
    q.push({0, s});
    while (!q.empty()) {
        _ d = q.top().first, u = q.top().second;
        q.pop();
        if (d != dist[u]) continue;
        for (_ jump : dg[u]) {
            c = 1;
            for (_ i = u + jump; i < n; i += jump, c++) {
                if (dist[i] > dist[u] + c) dist[i] = dist[u] + c, q.push({dist[i], i});
            }
            c = 1;
            for (_ i = u - jump; i >= 0; i -= jump, c++) {
                if (dist[i] > dist[u] + c) dist[i] = dist[u] + c, q.push({dist[i], i});
            } 
        }
    }
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:21:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     for (_ i = 0; i < m; ++i) scanf("%d %d", &b[i], &p[i]), dg[b[i]].insert(p[i]);
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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