Submission #1301893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301893		Ghulam_Junaid	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	1098 ms	31380 KiB

skyscraper

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

const int N = 3e4 + 10;
int n, m, b[N], p[N], ans = 1e9;
vector<int> at[N];
map<int, int> 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});
                if (!vis[u]){
                    vis[u] = 1;
                    for (int y : at[u]){
                        if (dist.find(u * N + y) != dist.end())
                            continue;
                        q.push({u, y});
                        dist[u * N + y] = dist[u * N + x];
                    }
                }
            }
        }
    }
}

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;
}

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