Submission #905780

#	Time	Username	Problem	Language	Result	Execution time	Memory
905780		Sir_Ahmed_Imran	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	460 ms	262144 KiB

skyscraper

                              ///~~~LOTA~~~///
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long 
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define MAXN 30001
int x[MAXN];
int y[MAXN];
int dist[MAXN];
unordered_set<int> b[MAXN];
unordered_map<int,int> a[MAXN];
void solve(){
    int n,m,o,p,q,r;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>x[i]>>y[i];
        b[x[i]].insert(y[i]);
    }
    for(int i=0;i<n;i++){
        dist[i]=INT_MAX;
        for(int j:b[i]){
            for(int k=i%j;k<n;k+=j){
                if(i==k) continue;
                if(a[i][k]==0)
                    a[i][k]=abs(i-k)/j;
                a[i][k]=min(a[i][k],abs(i-k)/j);
            }
        }
    }
    dist[x[0]]=0;
    priority_queue<pii,vector<pii>,greater<pii>> Q;
    Q.push({0,x[0]});
    while(!Q.empty()){
        p=Q.top().ss;
        q=Q.top().ff;
        Q.pop();
        if(p==x[1]){
            cout<<q;
            return;
        }
        if(q==dist[p]){
            for(pii i:a[p]){
                if(q+i.ss<dist[i.ff]){
                    dist[i.ff]=q+i.ss;
                    Q.push({q+i.ss,i.ff});
                }  
            }
        }
    }
    cout<<-1;
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    solve();
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:18:13: warning: unused variable 'o' [-Wunused-variable]
   18 |     int n,m,o,p,q,r;
      |             ^
skyscraper.cpp:18:19: warning: unused variable 'r' [-Wunused-variable]
   18 |     int n,m,o,p,q,r;
      |                   ^

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