Submission #251324

#	Time	Username	Problem	Language	Result	Execution time	Memory
251324		updown1	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1022 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;
pair<int,int> doge[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>>doge[i].first>>doge[i].second;
        lc[doge[i].first].push_back(i);
    }

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

    dist[doge[0].first]=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;
        if (ci == 1) {
            break;
        }
        //loops from current location to 0
        for(int i=0;doge[ci].first-i*doge[ci].second>=0;i++){
            //current location
            int cl=doge[ci].first-i*doge[ci].second;
            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;doge[ci].first+i*doge[ci].second<N;i++){
            int cl=doge[ci].first+i*doge[ci].second;
            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[doge[1].first]==INF){
        cout<<-1<<'\n';
    }else{
        cout<<dist[doge[1].first]<<'\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[doge[0].first].size();j++){
                 ~^~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:52:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int j=0;j<lc[cl].size();j++){
                             ~^~~~~~~~~~~~~~
skyscraper.cpp:62: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