제출 #1195448

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195448		Sarvar	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	418 ms	327680 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

struct edge_add {
    vector<int> to, nx;
    vector<int> hd;
    edge_add(int n) : hd(n, -1) {}
    inline void push(int u, int v, int w) {      // w ∈ {0,1}
        to.push_back((v << 1) | w);
        nx.push_back(hd[u]);
        hd[u] = static_cast<int>(to.size()) - 1;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<int> b(m), p(m);
    for (int i = 0; i < m; ++i) cin >> b[i] >> p[i];

    const int SQ = static_cast<int>(sqrt(n)) + 1;

    /* grafikni qurish */
    edge_add g(n);                      // avval faqat binolar (0..n-1)
    vector<int> dist(n, -1);

    /* kichik kuchlar (p ≤ SQ) uchun: har p va qoldiq r bo‘yicha tuzilma */
    vector<vector<char>> vis(SQ + 1);
    vector<unordered_map<int, int>> mp(SQ + 1);
    for (int i = 1; i <= SQ; ++i) vis[i].assign(i, 0);

    auto new_node = [&](edge_add &gr, vector<int> &d) -> int {
        int id = static_cast<int>(gr.hd.size());
        gr.hd.push_back(-1);
        d.push_back(-1);
        return id;
    };

    /* barchasini ketma‑ket quramiz */
    for (int i = 0; i < m; ++i) {
        int bi = b[i], pi = p[i];
        if (pi <= SQ) {                                 // kichik kuch
            int r = bi % pi;
            if (!vis[pi][r]) {                         // shu (pi,r) guruhi ilgari qurilmagan
                vis[pi][r] = 1;
                int prv = -1;
                for (int x = r; x < n; x += pi) {
                    int v = new_node(g, dist);         // guruh tuguni
                    g.push(v, x, 0);                   // tugun → bino (0)
                    if (prv != -1) {
                        g.push(v, prv, 1);             // qo‘shni tugunlar (1)
                        g.push(prv, v, 1);
                    }
                    mp[pi][x] = v;                     // (pi, x) ↦ id
                    prv = v;
                }
            }
            g.push(bi, mp[pi][bi], 0);                 // bino → guruh (0)
        } else {                                       // katta kuch (pi > SQ)
            int root = new_node(g, dist);
            g.push(bi, root, 0);                       // bino → ildiz (0)

            /* chapga zanjir */
            int u = root;
            for (int x = bi - pi; x >= 0; x -= pi) {
                int v = new_node(g, dist);
                g.push(u, v, 1);                       // zanjir bo‘ylab (1)
                g.push(v, x, 0);                       // tugun → bino (0)
                u = v;
            }
            /* o‘ngga zanjir */
            u = root;
            for (int x = bi + pi; x < n; x += pi) {
                int v = new_node(g, dist);
                g.push(u, v, 1);
                g.push(v, x, 0);
                u = v;
            }
        }
    }

    /* 0‑1 BFS (deque) */
    deque<int> dq;
    dist[b[0]] = 0;
    dq.push_front(b[0]);

    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();
        for (int e = g.hd[u]; e != -1; e = g.nx[e]) {
            int v = g.to[e] >> 1;
            int w = g.to[e] & 1;
            if (dist[v] == -1 || dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (w == 0) dq.push_front(v);
                else        dq.push_back(v);
            }
        }
    }

    cout << dist[b[1]] << '\n';        // dist[–1] bo‘lsa ‑1 chiqadi
    return 0;
}

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