Submission #1124139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124139		hieuhuy1402	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	813 ms	3524 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
const int INF = 0x3F3F3F3F;
const int MAX = 3e4 + 5;

int N, M, A, B;
vector<int> arr[MAX];
int dist[MAX];
bool vis[MAX];

int dijk() {
    
    fill(dist, dist + N + 1, INF);
    priority_queue< pii, vector<pii>, greater<pii> > pq;
    dist[A] = 0;
    pq.push({dist[A], A});
    
    while (!pq.empty()) {
        pii x = pq.top();
        pq.pop();
        int u = x.second;
        if (!vis[u]) {
            vis[u] = true;
            for (int i : arr[u]) {
                int v;
                for (int j = 1; u + (i * j) < N; j++) {
                    v = u + (i * j);
                    if (dist[u] + j < dist[v]) {
                        dist[v] = dist[u] + j;
                        pq.push({dist[v], v});
                    }
                }
                for (int j = -1; u + (i * j) >= 0; j--) {
                    v = u + (i * j);
                    if (dist[u] + abs(j) < dist[v]) {
                        dist[v] = dist[u] + abs(j);
                        pq.push({dist[v], v});
                    }
                }
            }
        }
    }
    
    return dist[B];
}

int main() {
    
    scanf("%d%d", &N, &M);
    int a, b;
    for (int i = 0; i < M; i++) {
        scanf("%d%d", &a, &b);
        arr[a].push_back(b);
        if (i == 0) {
            A = a;
        } else if (i == 1) {
            B = a;
        }
    }
    
    int ans = dijk();
    printf("%d", ans == INF ? -1 : ans);
    
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     scanf("%d%d", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         scanf("%d%d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~

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