Submission #1195296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195296		Sarvar	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	0 ms	328 KiB

skyscraper

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

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

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

    // 1) Collect unique powers <=√N and >√N separately:
    int S = sqrt(N);
    vector<vector<int>> powers(N);
    for(int i=0;i<M;i++){
        powers[ B[i] ].push_back(P[i]);
    }
    // 2) Assign IDs:
    //    - pos nodes: [0..N-1]
    //    - state nodes: subsequent
    int V = N;
    vector<unordered_map<int,int>> id_state(N);
    for(int b=0;b<N;b++){
        sort(powers[b].begin(), powers[b].end());
        powers[b].erase(unique(powers[b].begin(), powers[b].end()), powers[b].end());
        for(int p: powers[b]){
            id_state[b][p] = V++;
        }
    }

    // 3) Build graph
    vector<vector<pair<int,int>>> adj(V);
    auto addEdge = [&](int u,int v,int w){
        adj[u].emplace_back(v,w);
    };

    for(int b=0;b<N;b++){
        for(int p: powers[b]){
            int u = id_state[b][p];
            // jump left/right
            int nb = b + p;
            if(nb<N) addEdge(u, id_state[nb][p], 1);
            nb = b - p;
            if(nb>=0) addEdge(u, id_state[nb][p], 1);
            // to dummy(b)
            addEdge(u, b, 1);
        }
        // from dummy(b) to each (b,p)
        for(int p: powers[b]){
            addEdge(b, id_state[b][p], 0);
        }
    }

    // 4) Dijkstra
    vector<ll> dist(V, INF);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
    int start = id_state[B[0]][P[0]];
    int target = id_state[B[1]][P[1]];
    dist[start] = 0;
    pq.push({0, start});
    while(!pq.empty()){
        auto [d,u] = pq.top(); pq.pop();
        if(d > dist[u]) continue;
        for(auto &e: adj[u]){
            int v = e.first, w = e.second;
            if(dist[v] > d + w){
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }

    ll ans = dist[target];
    cout << (ans==INF? -1 : ans) << "\n";
    return 0;
}

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