Submission #757450

#	Time	Username	Problem	Language	Result	Execution time	Memory
757450		Trisanu_Das	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	650 ms	3712 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() {
    cin >> N >> M;
    int a, b;
    for (int i = 0; i < M; i++) {
        cin >> 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);
}

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