Submission #1271984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271984		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 = 1e18;

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

int N, M;
int B[30009], P[30009];
ll dista[30009];

const int MAXP = 30005;
// group[p][r] = danh sách doge có sức mạnh p và B % p = r
vector<vector<int>> group[MAXP];

void Dijkstra() {
    for (int i = 0; i < M; i++) dista[i] = INF;
    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) {
            cout << cost;
            return;
        }

        int p = P[u];
        int r = B[u] % p;

        auto &vec = group[p][r];
        if (!vec.empty()) {
            for (int v : vec) {
                if (v == u) continue;
                ll w = abs(B[u] - B[v]) / p;
                if (dista[v] > cost + w) {
                    dista[v] = cost + w;
                    pq.push({dista[v], v});
                }
            }
            vec.clear(); // clear để nhóm này không bị duyệt lại
        }
    }
    cout << -1;
}

void solve() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> B[i] >> P[i];
        if (group[P[i]].empty()) {
            group[P[i]].resize(P[i]); // khởi tạo các nhóm dư 0..P[i]-1
        }
        group[P[i]][B[i] % P[i]].push_back(i);
    }
    Dijkstra();
}

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

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