Submission #1226601

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226601		Bui_Quoc_Cuong	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	64 ms	17736 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
int n, m;
struct bg{
    int pos, jump;
} a[30005];
namespace sub1234{
    vector <int> pos[30005];
    #define data array <int, 3>
    int dist[2005][2005]; 
    void solve(){
        for(int i = 1; i <= m; i++) pos[a[i].pos].push_back(i);
        memset(dist, 0x3f, sizeof dist);
        priority_queue <data, vector <data>, greater <data>> pq;
        pq.push({dist[a[1].pos][a[1].jump] = 0, a[1].pos, a[1].jump});
        while(!pq.empty()){
            int u = pq.top()[1], jump = pq.top()[2], cost = pq.top()[0];
            pq.pop();
            if(cost > dist[u][jump]) continue;
            if(u == a[2].pos) return void(cout << cost);
            if(u - jump >= 1 && dist[u - jump][jump] > cost + 1){
                dist[u - jump][jump] = cost + 1;
                pq.push({cost + 1, u - jump, jump});
            } 
            if(u + jump <= n && dist[u + jump][jump] > cost + 1){
                dist[u + jump][jump] = cost + 1;
                pq.push({cost + 1, u + jump, jump});
            }
            for(int &id : pos[u]){
                if(dist[u][a[id].jump] > cost){
                    dist[u][a[id].jump] = cost;
                    pq.push({cost, u, a[id].jump});
                }
            }
        }
        cout << - 1;
    }
}
namespace sub5{

    void solve(){
        
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);   
    #define taskname "kieuoanh"
    if(fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout);
    }
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        cin >> a[i].pos >> a[i].jump;
        a[i].pos++;
    }
    if(n <= 2000 && m <= 30000) return sub1234::solve(), 0;
    ///return sub5::solve(), 0;
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:50:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:50:53: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout);
      |                                              ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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