Submission #1272001

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

skyscraper

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

using namespace std;
using ll = long long;
const ll oo = (ll)1e18;
const int MAXM = 30009;

int N, M;
int B[MAXM], P[MAXM];
vector<pair<int,ll>> adj[MAXM];
ll dista[MAXM];

void Dijkstra() {
    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[0] = 0;
    pq.push({0, 0});

    while (!pq.empty()) {
        auto [cost, u] = pq.top();
        pq.pop();
        if (cost != dista[u]) continue;
        if (u == 1) { // đích theo ý bạn (index 1)
            cout << cost << '\n';
            return;
        }
        for (auto &e : adj[u]) {
            int v = e.first;
            ll w = e.second;
            if (dista[v] > cost + w) {
                dista[v] = cost + w;
                pq.push({dista[v], v});
            }
        }
    }
    cout << -1 << '\n';
}

void solve() {
    cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        adj[i].clear();
    }

    // đọc input và tạo danh sách các p xuất hiện
    unordered_map<int, vector<int>> sources; // p -> list index i có P[i]==p
    sources.reserve(M * 2);
    for (int i = 0; i < M; ++i) {
        cin >> B[i] >> P[i];
        sources[P[i]].push_back(i);
    }

    // Với mỗi p xuất hiện, nhóm tất cả trạm theo B[j] % p (tất cả j)
    for (auto &pr : sources) {
        int p = pr.first;
        // build groups: rem -> list of indices j (tất cả trạm j)
        unordered_map<int, vector<int>> groups;
        groups.reserve(M * 2 / max(1, (int)sources.size()));
        for (int j = 0; j < M; ++j) {
            int rem = B[j] % p;
            groups[rem].push_back(j);
        }
        // cho mỗi nguồn i có P[i]==p, nối đến mọi j trong cùng rem
        for (int i_idx : pr.second) {
            int rem_i = B[i_idx] % p;
            auto &vec = groups[rem_i];
            for (int j : vec) {
                if (j == i_idx) continue;
                ll w = llabs((ll)B[i_idx] - (ll)B[j]) / p; // chia hết vì cùng rem mod p
                adj[i_idx].push_back({j, w});
            }
        }
    }

    Dijkstra();
}

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

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