Submission #1272011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272011		pvb.tunglam	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	1 ms	572 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)4e18;

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

    int N, M;
    cin >> N >> M;
    vector<int> B(M), P(M);
    for(int i = 0; i < M; i++){
        cin >> B[i] >> P[i];
    }

    // Tính SQ = sqrt(N) ngưỡng
    int SQ = max(1, (int)(sqrt(N)) );

    // pos_at[x] = list các doge tại vị trí x
    vector<vector<int>> pos_at(N);
    for(int i = 0; i < M; i++){
        pos_at[B[i]].push_back(i);
    }

    // Với các P[u] nhỏ ≤ SQ: ta sẽ lưu trạng thái (position, p)
    // dis_small[position][p] = tối thiểu bước để tới position với khả năng nhảy p
    // Với P[u] > SQ: ta dùng trạng thái đặc biệt cho mỗi doge

    // dis_pos_p: dùng map hoặc vector size N * (SQ+1), large
    vector<vector<ll>> dis_small(N, vector<ll>(SQ+1, INF));
    // dis_doge for doges with P > SQ: dis_doge[i] = best cost khi gửi tin tới doge i
    vector<ll> dis_doge(M, INF);

    // priority_queue hoặc deque nếu dùng 0-1 BFS? Nhưng cost nhảy lớn → Dijkstra
    using T = pair<ll, pair<int,int>>; 
    // Pair: (cost, (type, id)), type 0 = small-state (pos,p), type 1 = big-doge (doge index)
    // Với type 0: id = pos * (SQ+1) + p, nhưng chúng ta dùng struct

    struct State {
        ll cost;
        int type; // 0 = small, 1 = big doge
        int id;   // if type=0: encode pos, p; if type=1: doge index
        int p_or_unused; // chỉ dùng khi type=0, là p
    };
    struct Cmp {
        bool operator()(State const &a, State const &b) const {
            return a.cost > b.cost;
        }
    };

    priority_queue<State, vector<State>, Cmp> pq;

    // Khởi đầu: doge 0 có P[0]
    if(P[0] <= SQ){
        if(dis_small[B[0]][P[0]] > 0){
            dis_small[B[0]][P[0]] = 0;
            pq.push({0, 0, B[0], P[0]});
        }
    } else {
        if(dis_doge[0] > 0){
            dis_doge[0] = 0;
            pq.push({0, 1, 0, 0}); // dùng p_or_unused = unused
        }
    }

    // Các boolean để mark truyền tin khi có doge tại cùng position
    vector<bool> used_pos_small(N * (SQ+1), false);
    vector<bool> used_pos_big(M, false); // để khi doge lớn được xử lý truyền tin

    while(!pq.empty()){
        State cur = pq.top(); pq.pop();
        ll d = cur.cost;
        int type = cur.type;
        if(type == 1 && cur.id == 1){
            // tới doge 1
            cout << d << "\n";
            return 0;
        }

        if(type == 0){
            int pos = cur.id;
            int p = cur.p_or_unused;
            if(d > dis_small[pos][p]) continue;

            // 1) Nhảy từ (pos, p) tới (pos ± p, p) nếu trong [0,N)
            for(int dir : {+1, -1}){
                int pos2 = pos + dir * p;
                if(pos2 >= 0 && pos2 < N){
                    ll nd = d + 1;
                    if(dis_small[pos2][p] > nd){
                        dis_small[pos2][p] = nd;
                        pq.push({nd, 0, pos2, p});
                    }
                }
            }

            // 2) Nếu có doge(s) tại position pos, truyền tin tới các doge nhỏ hoặc lớn
            // Man truyền tin = 0 cost, tới doge v tại pos
            for(int doge_v : pos_at[pos]){
                // v có P[v]
                if(P[doge_v] <= SQ){
                    // chuyển sang trạng thái small (pos, P[v])
                    if(dis_small[pos][P[doge_v]] > d){
                        dis_small[pos][P[doge_v]] = d;
                        pq.push({d, 0, pos, P[doge_v]});
                    }
                } else {
                    // truyền tin tới big doge
                    if(dis_doge[doge_v] > d){
                        dis_doge[doge_v] = d;
                        pq.push({d, 1, doge_v, 0});
                    }
                }
            }

        } else { // type == 1: state là “tin được ở doge u, với P[u] lớn”
            int u = cur.id;
            if(d > dis_doge[u]) continue;

            int step = P[u];
            int posu = B[u];

            // 1) từ doge, nhảy tới các vị trí posu ± k*step
            // enumerate cả hai hướng
            // mỗi bước mất cost = k
            // chúng ta muốn chuyển sang trạng thái small hoặc doge nếu gặp doge

            // hướng phải
            for(ll x = posu + step, k = 1; x < N; x += step, k++){
                ll nd = d + k;
                // trạng thái small (x, step) nếu step ≤ SQ; nếu step > SQ, chỉ có thể truyền tin khi gặp doge
                if(step <= SQ){
                    if(dis_small[x][step] > nd){
                        dis_small[x][step] = nd;
                        pq.push({nd, 0, (int)x, step});
                    }
                }
                // nếu có doge ở x
                for(int doge_v : pos_at[x]){
                    if(dis_doge[doge_v] > nd){
                        dis_doge[doge_v] = nd;
                        pq.push({nd, 1, doge_v, 0});
                    }
                }
            }
            // hướng trái
            for(ll x = posu - step, k = 1; x >= 0; x -= step, k++){
                ll nd = d + k;
                if(step <= SQ){
                    if(dis_small[x][step] > nd){
                        dis_small[x][step] = nd;
                        pq.push({nd, 0, (int)x, step});
                    }
                }
                for(int doge_v : pos_at[x]){
                    if(dis_doge[doge_v] > nd){
                        dis_doge[doge_v] = nd;
                        pq.push({nd, 1, doge_v, 0});
                    }
                }
            }
        }
    }

    // Nếu không tới doge 1
    cout << -1 << "\n";
    return 0;
}

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