제출 #251334

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
251334		updown1	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	794 ms	3956 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]));
    }*/
    pq.push(make_pair(0, dogea[0]));

    dist[dogea[0]]=0;
    while(!pq.empty()){
        //cd is number of jumps and ci is the current index
        int cd=-pq.top().first;
        int si=pq.top().second;
        pq.pop();
        //if that dog has already been visited there is no need to check again
        if(vdoge[si]) continue;
        vdoge[si]=true;

        for(int j=0;j<lc[si].size();j++){
            int ci = lc[si][j];
            //loops from current location to 0
            for(int i=0, cl=dogea[ci];cl>=0;i++, cl -= dogeb[ci]){
                //current location
                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]));
                    }*/
                    pq.push(make_pair(-dist[cl],cl));
                }
            }
            //to N-1
            for(int i=1, cl=dogea[ci]+dogeb[ci];cl<N;cl += dogeb[ci], i++){
                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]));
                    }*/
                    pq.push(make_pair(-dist[cl],cl));
                }
            }
        }
    }
    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
*/

컴파일 시 표준 에러 (stderr) 메시지

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

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