Submission #146041

#	Time	Username	Problem	Language	Result	Execution time	Memory
146041		str0ct	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	137 ms	5732 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
using pii=pair <int,int>;
int vis[30303];
int N,M;
pair <int,int> ipt[30303];
vector <int> V[30303];
priority_queue<pii,vector<pii>,greater<pii> > pq;
void dijkstra(){
    pq.push({0,ipt[0].first});
    vis[ipt[0].first]=0;
    while(!pq.empty()){
        int a=pq.top().first,b=pq.top().second;
        pq.pop();
        if(a<=vis[b]){
            for(auto i:V[b]){
                for(int k=1;b+i*k<N;k++){
                        if(vis[b+i*k]>a+k){
                            pq.push({a+k,b+i*k});
                            vis[b+i*k]=a+k;
                        }
                        auto it=lower_bound(V[b+i*k].begin(),V[b+i*k].end(),i);
                        if(it!=V[b+i*k].end()&&*it==i)break;
                }
                for(int k=1;b-i*k>=0;k++){
                        if(vis[b-i*k]>a+k){
                            pq.push({a+k,b-i*k});
                            vis[b-i*k]=a+k;
                        }
                        auto it=lower_bound(V[b-i*k].begin(),V[b-i*k].end(),i);
                        if(it!=V[b-i*k].end()&&*it==i)break;
                }
            }
        }
    }
}

int main(){
    fill(vis,vis+30303,1010101010);
    scanf("%d%d",&N,&M);
    for(int i=0;i<M;i++){
        scanf("%d%d",&ipt[i].first,&ipt[i].second);
        V[ipt[i].first].push_back(ipt[i].second);
    }
    for(int i=0;i<30003;i++){
        sort(V[i].begin(),V[i].end());
        V[i].erase(unique(V[i].begin(),V[i].end()),V[i].end());
    }
    dijkstra();
    if(vis[ipt[1].first]!=1010101010)printf("%d",vis[ipt[1].first]);
    else puts("-1");
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&N,&M);
     ~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&ipt[i].first,&ipt[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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