Submission #1256250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256250		nanaseyuzuki	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	72 ms	25024 KiB

skyscraper

#include <bits/stdc++.h>
/*
    --> Author: Kazuki_Hoshino__8703 <--
    I love Nanasaki Ai ☆*: .。. o(≒＿≒)o .。.:☆
*/
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long
using namespace std;

const int mn = 3e4 + 5, bm = (1 << 11) + 1, mod = 1532023, offset = 5e4;
const int inf = 1e9, base = 311;

int n, m, a[mn], b[mn], check[mn][180];
int d[mn];
vector <int> speed[mn];

void dijkstra(){
    priority_queue<pii, vector<pii>, greater<pii> > pq;
    fill(&d[0], &d[0] + mn, inf);
    d[a[0]] = 0;
    pq.push({d[a[0]], a[0]});
    while(pq.size()){
        auto[c, u] = pq.top();
        pq.pop();
        if(c > d[u]) continue;
        for(auto sp : speed[u]){
            for(int i = 1; u + i * sp < n; i++){
                if(sp <= 179 && check[u + i * sp][sp]) break;
                if(d[u + i * sp] > d[u] + i){
                    d[u + i * sp] = d[u] + i;
                    pq.push({d[u + i * sp], u + i * sp});
                }
                if(sp <= 179) check[u + i * sp][sp] = 1;
            }
            for(int i = 1; u - i * sp >= 0; i++){
                if(sp <= 179 && check[u - i * sp][sp]) break;
                if(d[u - i * sp] > d[u] + i){
                    d[u - i * sp] = d[u] + i;
                    pq.push({d[u - i * sp], u - i * sp});
                }
                if(sp <= 179) check[u - i * sp][sp] = 1;
            }
        }
    }
    if(d[a[1]] == inf) d[a[1]] = -1;
    cout << d[a[1]] << '\n';
}

void solve(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> a[i] >> b[i];
        speed[a[i]].push_back(b[i]);
    }
    dijkstra();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if(fopen("ROBOT.INP", "r")) {
        freopen("ROBOT.INP", "r", stdin);
        freopen("ROBOT.OUT", "w", stdout);
    }
    int t = 1;
    // cin >> t;
    while(t--) {
        solve();
    }
}

Compilation message (stderr)

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

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