Submission #251326

#	Time	Username	Problem	Language	Result	Execution time	Memory
251326		updown1	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1031 ms	3192 KiB

skyscraper

/*
Code by @marlov
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

#define INF 200000000
#define maxV 30005

int N,M;
int dogea[maxV], dogeb[maxV];
//distance to location 0-N-1 inclusive
int dist[maxV];
bool vdoge[maxV];
priority_queue< pair<int,int> > pq;
//location contains array
vector<int> lc[maxV];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M;
    fill(dist,dist+N,INF);
    for(int i=0;i<M;i++){
        cin>>dogea[i]>>dogeb[i];
        lc[dogea[i]].push_back(i);
    }

    for(int j=0;j<lc[dogea[0]].size();j++){
        pq.push(make_pair(0,lc[dogea[0]][j]));
    }

    dist[dogea[0]]=0;
    while(!pq.empty()){
        //cd is number of jumps and ci is the current index
        int cd=-pq.top().first;
        int ci=pq.top().second;
        pq.pop();
        //if that dog has already been visited there is no need to check again
        if(vdoge[ci]) continue;
        vdoge[ci]=true;
        //loops from current location to 0
        for(int i=0;dogea[ci]-i*dogeb[ci]>=0;i++){
            //current location
            int cl=dogea[ci]-i*dogeb[ci];
            if(cd+i<dist[cl]){
                dist[cl]=cd+i;
                for(int j=0;j<lc[cl].size();j++){
                    pq.push(make_pair(-dist[cl],lc[cl][j]));
                }
            }
        }
        //to N-1
        for(int i=1;dogea[ci]+i*dogeb[ci]<N;i++){
            int cl=dogea[ci]+i*dogeb[ci];
            if(cd+i<dist[cl]){
                dist[cl]=cd+i;
                for(int j=0;j<lc[cl].size();j++){
                    pq.push(make_pair(-dist[cl],lc[cl][j]));
                }
            }
        }
    }
    if(dist[dogea[1]]==INF){
        cout<<-1<<'\n';
    }else{
        cout<<dist[dogea[1]]<<'\n';
    }
    return 0;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1,n=0?)
	* do smth instead of nothing and stay organized
*/

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:30:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<lc[dogea[0]].size();j++){
                 ~^~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:49:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int j=0;j<lc[cl].size();j++){
                             ~^~~~~~~~~~~~~~
skyscraper.cpp:59:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int j=0;j<lc[cl].size();j++){
                             ~^~~~~~~~~~~~~~

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