Submission #1272028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272028		pvb.tunglam	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	36 / 100	1097 ms	41392 KiB

skyscraper

#include <bits/stdc++.h>
#define hash _hash_
#define left _left_
#define y1 _y1_

using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const ll oo = 1e18;

/*----------- I alone decide my fate! ----------*/
   /* Chiec den ong sao, sao 5 canh tuoi mau */

const int MAXM = 30005;
const int SQ = 200;

int N, M;
int a[MAXM], p[MAXM];
ll dista[MAXM];

vector<int> rem[SQ+5][SQ+5];   // rem[j][r] = list of indices có a[i] % j = r
vector<int> pos[30009];        // pos[x] = list of indices có a[i] = x

void Dijkstra(int st, int ed) {
    for (int i = 0; i < M; i++) dista[i] = oo;
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;

    dista[st] = 0;
    pq.push({0, st});

    int max_a = *max_element(a, a+M);

    while (!pq.empty()) {
        auto [cost, u] = pq.top(); pq.pop();
        if (cost != dista[u]) continue;
        if (u == ed) {
            cout << cost;
            return;
        }
        if (p[u] <= SQ) {
            for (int v : rem[p[u]][a[u] % p[u]]) {
                ll w = abs(a[u] - a[v]) / p[u];
                if (dista[v] > cost + w) {
                    dista[v] = cost + w;
                    pq.push({dista[v], v});
                }
            }
        } else {
            for (int x = a[u] % p[u]; x <= max_a; x += p[u]) {
                for (int v : pos[x]) {
                    ll w = abs(a[u] - a[v]) / p[u];
                    if (dista[v] > cost + w) {
                        dista[v] = cost + w;
                        pq.push({dista[v], v});
                    }
                }
            }
        }
    }
    cout << -1;
}

void solve() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> a[i] >> p[i];
        for (int j = 1; j <= SQ; j++) {
            rem[j][a[i] % j].push_back(i);
        }
        pos[a[i]].push_back(i);
    }
    Dijkstra(0, 1); // từ thang máy đầu tiên đến thang máy thứ hai
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    solve();
    return 0;
}

/*
  How can you see into my eyes, like open doors?
  Leading you down into my core, where I've become so numb
  Without a soul, my spirit's sleeping somewhere cold
  Until you find it here and bring it back home!
  Wake me up! Wake me up inside
  Cant wake up? Wake me up inside
*/

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