제출 #1271990

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271990		pvb.tunglam	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	1 ms	572 KiB

skyscraper

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

using namespace std;
using ll = long long;
const ll INF = (ll)4e18;

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

int N, M;
ll B[30009];
int P[30009];
vector<pair<int,int>> adj[30009]; // adj[u] = {v, weight}
ll dista[30009];

void solve() {
    if (!(cin >> N >> M)) return;
    for (int i = 0; i < M; ++i) {
        cin >> B[i] >> P[i];
    }

    if (M < 2) { // không có doge 1
        cout << -1;
        return;
    }

    // order: tất cả chỉ số doge, sẽ sort theo P, rem = B%P, rồi theo B
    vector<int> order(M);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
        if (P[i] != P[j]) return P[i] < P[j];
        int ri = (int)(B[i] % P[i]);
        int rj = (int)(B[j] % P[j]);
        if (ri != rj) return ri < rj;
        return B[i] < B[j];
    });

    // duyệt theo từng block có cùng P, trong block tách theo rem rồi nối adjacent
    int idx = 0;
    while (idx < M) {
        int start = idx;
        int p = P[order[idx]];
        while (idx < M && P[order[idx]] == p) ++idx;
        // block [start, idx)
        int s = start;
        while (s < idx) {
            int rem = (int)(B[order[s]] % p);
            int t = s + 1;
            while (t < idx && (int)(B[order[t]] % p) == rem) ++t;
            // indices from s..t-1 have same (p, rem) and are sorted by B because of comparator
            for (int k = s; k + 1 < t; ++k) {
                int u = order[k];
                int v = order[k+1];
                ll gap = B[v] - B[u]; // >= 0
                ll w = gap / p; // chia hết vì cùng remainder
                // thêm cạnh hai hướng
                adj[u].push_back({v, (int)w});
                adj[v].push_back({u, (int)w});
            }
            s = t;
        }
    }

    // Dijkstra từ doge 0 tới doge 1
    for (int i = 0; i < M; ++i) dista[i] = INF;
    using pli = pair<ll,int>;
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    dista[0] = 0;
    pq.push({0, 0});
    while (!pq.empty()) {
        auto cur = pq.top(); pq.pop();
        ll d = cur.first;
        int u = cur.second;
        if (d != dista[u]) continue;
        if (u == 1) break; // đã tìm được khoảng cách ngắn nhất tới doge 1
        for (auto &e : adj[u]) {
            int v = e.first;
            ll w = (ll)e.second;
            if (dista[v] > d + w) {
                dista[v] = d + w;
                pq.push({dista[v], v});
            }
        }
    }

    if (dista[1] == INF) cout << -1;
    else cout << dista[1];
}

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

/*
  Wake me up! Wake me up inside
*/

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