Submission #960690

#	Time	Username	Problem	Language	Result	Execution time	Memory
960690		3omar_ahmed	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	563 ms	148176 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std ;
#define endl '\n'
#define all(a) a.begin() , a.end()
#define alr(a) a.rbegin() , a.rend()
const int N = 30004 * 175, M = 175;
vector < int > dis(N, 1e9);
vector < vector < pair < int , int >>> adj(N);
int conv(int i, int j, int n) {
    return (i * M + j);
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

    int n, m;
    cin >> n >> m;
    pair < int , int > first, second;
    vector < vector < int >> arr(1 + n);
    set < pair < int , int >> s;
    for(int i = 0 ; i < m ; i++) {
        int a, b;
        cin >> a >> b;
        if(b < n) s.insert({a, b});
        if(i == 0) {
            first = {a, b};
        } else if(i == 1) {
            second = {a, b};
        }
    }
    for(auto i : s) {
        arr[i.first].push_back(i.second);
    }
    int st = first.first * M;
    priority_queue < pair < int , int >> pq;
    pq.push({0, st});
    dis[st] = 0; 
    while(pq.size()) {
        auto top = pq.top();
        pq.pop();
        top.first *= -1;
        if(top.first != dis[top.second])
            continue;
        int i = top.second / M;
        int j = top.second % M;
        // cout << i << " " << j << " " << top.first << endl;
        if(j == 0) {
            for(auto nxt : arr[i]) {
                if(nxt < M && dis[conv(i, nxt, n)] > top.first) {
                    dis[conv(i, nxt, n)] = top.first;
                    pq.push({-dis[conv(i, nxt, n)], conv(i, nxt, n)});
                } else if(nxt >= M) {
                    for(int j = 1 ; j <= n ; j++) {
                        if(i + j * nxt < n && dis[conv(i + j * nxt, 0, n)] > top.first + j) {
                            dis[conv(i + j * nxt, 0, n)] = top.first + j;
                            pq.push({-dis[conv(i + j * nxt, 0, n)], conv(i + j * nxt, 0, n)});
                        }
                        if(i + j * nxt >= n) break;
                    }
                    for(int j = 1 ; j <= n ; j++) {
                        if(i - j * nxt >= 0 && dis[conv(i - j * nxt, 0, n)] > top.first + j) {
                            dis[conv(i - j * nxt, 0, n)] = top.first + j;
                            pq.push({-dis[conv(i - j * nxt, 0, n)], conv(i - j * nxt, 0, n)});
                        }
                        if(i - j * nxt < 0) break;
                    }
                }
            }
        } else {
            if(i + j < n && dis[conv(i + j, j, n)] > top.first + 1) {
                dis[conv(i + j, j, n)] = top.first + 1;
                pq.push({-dis[conv(i + j, j, n)], conv(i + j, j, n)});
            }
            if(i + j < n && dis[conv(i + j, 0, n)] > top.first + 1) {
                dis[conv(i + j, 0, n)] = top.first + 1;
                pq.push({-dis[conv(i + j, 0, n)], conv(i + j, 0, n)});
            }
            if(i - j >= 0 && dis[conv(i - j, j, n)] > top.first + 1) {
                dis[conv(i - j, j, n)] = top.first + 1;
                pq.push({-dis[conv(i - j, j, n)], conv(i - j, j, n)});
            }
            if(i - j >= 0 && dis[conv(i - j, 0, n)] > top.first + 1) {
                dis[conv(i - j, 0, n)] = top.first + 1;
                pq.push({-dis[conv(i - j, 0, n)], conv(i - j, 0, n)});
            }
        }
    }
    int ans = 1e9;
    for(int i = 0 ; i < M ; i++) {
        ans = min(ans, dis[second.first * M + i]);
    }
    if(ans >= 1e8) ans = -1;
    cout << ans << endl;
    return 0 ;
}

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