Submission #1226607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226607		Bui_Quoc_Cuong	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	577 ms	6584 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{
    int dp[30005];
    vector <int> pos[30005];
    void solve(){
        memset(dp, 0x3f, sizeof dp);
        for(int i = 1; i <= m; i++) pos[a[i].pos].push_back(a[i].jump);
        for(int i = 1; i <= n; i++){
            sort(pos[i].begin(), pos[i].end());
            // pos[i].unique(pos[i].begin(), pos[i].end()) - pos[i].begin();
            unique(pos[i].begin(), pos[i].end()) - pos[i].begin();
        }
        priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> pq;
        pq.push({dp[a[1].pos] = 0, a[1].pos});
        while(!pq.empty()){
            int u = pq.top().second, cost = pq.top().first;
            pq.pop();
            if(cost > dp[u]) continue;
            if(u == a[2].pos) return void(cout << cost);
            for(int &p : pos[u]){
                for(int v = u + p, w = 1; v <= n; v+= p, w++){
                    if(dp[v] > cost + w){
                        dp[v] = cost + w;
                        pq.push({dp[v], v});
                    }
                }
                for(int v = u - p, w = 1; v >= 1; v-= p, w++){
                    if(dp[v] > cost + w){
                        dp[v] = cost + w;
                        pq.push({dp[v], v});
                    }
                }
            }
        }
        cout << - 1;
    }
}
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:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:80:53: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         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: 43 / 43