Submission #1168457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168457		ZeroCool	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	0 ms	328 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define ll long long
#define ld long double
#define all(v) v.begin(),v.end()
#define ar array

const int M = 1e6;
const int N = 4e5 + 20;
const int LOG = 61;
const int INF = 1e18;
const int MOD = 1e9 + 7;
const ld EPS = 1e-9;
inline void mm(int &x){x = (x % MOD + MOD) % MOD;}
inline void chmin(int &x, int y){x = min(x, y);}
inline void chmax(int &x, int y){x = max(x, y);}

#pragma GCC optimize("unroll-loops,O3")


void orz(){
    int n, m;
    cin>>n>>m;
    vector<int> g[n];
    int s = -1, e = -1;
    while(m--){
        int a, b;
        cin>>a>>b;
        if(s == -1)s = a;
        else if(e == -1)e = a;
        if(b < n)g[a].push_back(b);
    }
    priority_queue<ar<int, 2> > pq;
    pq.push({s, 0});
    bool vis[n] = {0};
    while(pq.size()){
        auto [d, x] = pq.top();
        pq.pop();
        if(vis[x])continue;
        vis[x] = 1;
        if(e == x){
            cout<<-d;
            return;
        }
        for(auto u: g[x]){
            for(int i = 1;x + u * i < n;i++){
                int y = x + u * i;
                if(!vis[y])pq.push({d - i, y});
            }
            for(int i = 1;x - u * i >= 0;i++){
                int y = x - u * i;
                if(!vis[y])pq.push({d - i, y});
            }
        }
    }
}

signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
   
    int t = 1;
    //cin>>t;
    while(t--)orz();
} 

Compilation message (stderr)

skyscraper.cpp:12:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   12 | const int INF = 1e18;
      |                 ^~~~

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