Submission #1301922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301922		Ghulam_Junaid	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	1100 ms	103280 KiB

skyscraper

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

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};


const int N = 3e4 + 10;
int n, m, b[N], ite, p[N], ans = 1e9;
vector<int> at[N];
unordered_map<long long, int, custom_hash> dist;
bool vis[N];

void f(int v, int e){
    queue<pair<int, int>> q;
    for (int x : at[v]){
        q.push({v, x});
        dist[v * N + x] = 0;
    }
    vis[v] = 1;

    while (!q.empty()){
        auto [v, x] = q.front();
        q.pop();

        if (v == e){
            ans = dist[v * N + x];
            break;
        }

        for (int u : {v + x, v - x}){
            if (u < 0 or u >= n) continue;
            if (dist.find(u * N + x) == dist.end())
                dist[u * N + x] = 1e9;
            if (dist[u * N + x] > dist[v * N + x] + 1){
                dist[u * N + x] = dist[v * N + x] + 1;
                q.push({u, x});
                ite++;
                if (!vis[u]){
                    vis[u] = 1;
                    for (int y : at[u]){
                        if (dist.find(u * N + y) != dist.end())
                            continue;
                        q.push({u, y});
                        ite++;
                        dist[u * N + y] = dist[u * N + x];
                    }
                }
            }
        }
        if (ite > 1e7) cout << 1/0 << endl;
    }
}

int main(){
    cin >> n >> m;
    for (int i = 0; i < m; i ++){
        cin >> b[i] >> p[i], at[b[i]].push_back(p[i]);
    }
    f(b[0], b[1]);
    if (ans == 1e9) ans = -1;
    cout << ans << endl;
}

Compilation message (stderr)

skyscraper.cpp: In function 'void f(int, int)':
skyscraper.cpp:63:33: warning: division by zero [-Wdiv-by-zero]
   63 |         if (ite > 1e7) cout << 1/0 << endl;
      |                                ~^~

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