제출 #1271999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271999		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 oo = 1e18;

/*----------- I alone decide my fate! ----------*/

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

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) { // giữ nguyên mục tiêu như bạn viết (node index 1)
            cout << cost;
            return;
        }
        for (auto [v, w] : adj[u]) {
            if (dista[v] > cost + w) {
                dista[v] = cost + w;
                pq.push({dista[v], v});
            }
        }
    }
    cout << -1;
}

vector<int> buckets[30009];

void solve() {
    cin >> N >> M;
    // reset data structures
    for (int i = 0; i <= N; ++i) buckets[i].clear();
    for (int i = 0; i < M; ++i) adj[i].clear();

    for (int i = 0; i < M; i++) {
        cin >> B[i] >> P[i];
        if (P[i] <= N && P[i] >= 1) buckets[P[i]].push_back(i);
        else {
            // phòng trường hợp P[i] > N (không hợp lý với ý tưởng), vẫn lưu vào bucket rời
            if (P[i] >= 30009) {
                // rare, ignore grouping -> no edges from this node by grouping method
            } else buckets[P[i]].push_back(i);
        }
    }

    // Với mỗi p, nhóm các trạm theo (B % p), sort theo B và nối các cặp kề nhau
    for (int p = 1; p <= N; ++p) {
        if (buckets[p].empty()) continue;
        unordered_map<int, vector<pair<int,int>>> groups;
        groups.reserve(buckets[p].size()*2);
        for (int idx : buckets[p]) {
            int rem = B[idx] % p;
            groups[rem].push_back({B[idx], idx});
        }
        for (auto &pr : groups) {
            auto &vec = pr.second;
            sort(vec.begin(), vec.end()); // sort theo B tự động
            for (int k = 0; k + 1 < (int)vec.size(); ++k) {
                int u = vec[k].second;
                int v = vec[k+1].second;
                ll delta = (ll)vec[k+1].first - (ll)vec[k].first; // khoảng cách vị trí
                ll w = delta / p; // số bước (đảm bảo chia hết vì cùng class mod)
                // lưu weight dưới dạng int (an toàn nếu weights nhỏ), hoặc cast cẩn thận
                adj[u].push_back({v, (int)w});
                adj[v].push_back({u, (int)w});
            }
        }
    }

    Dijkstra();
}

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: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43