Submission #1301884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301884		Ghulam_Junaid	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	1002 ms	30972 KiB

skyscraper

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

const int N = 3e4 + 10;
int n, m, b[N], p[N];
vector<int> at[N];
map<pair<int, int>, int> dist;
bool vis[N];

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

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

        for (int u : {v + x, v - x}){
            if (u < 0 or u >= n) continue;
            if (dist.find({u, x}) == dist.end())
                dist[{u, x}] = 1e9;
            if (dist[{u, x}] > dist[{v, x}] + 1){
                dist[{u, x}] = dist[{v, x}] + 1;
                q.push({u, x});
                if (!vis[u]){
                    vis[u] = 1;
                    for (int y : at[u]){
                        q.push({u, y});
                        dist[{u, y}] = dist[{u, 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]);
    int ans = 1e9;
    for (auto [P, d] : dist)
        if (P.first == b[1] and ans > d)
            ans = d;
    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