제출 #928041

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
928041		AlphaMale06	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	395 ms	4312 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define F first
#define S second

const int N = 30010;
const int inf = 1e9;
int dist[N];
bool mark[N];
vector<int> all[N];
vector<int> jumps[N];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> st;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    int s, t;
    for(int i=0; i< m; i++){
        int a, b;
        cin >> a >> b;
        if(i==0)s=a;
        if(i==1)t=a;
        all[a].pb(b);
    }
    for(int i=0; i< n; i++){
        sort(all[i].begin(), all[i].end());
        if(all[i].size()){
            jumps[i].pb(all[i][0]);
            for(int j=1; j<all[i].size(); j++){
                if(all[i][j]!=all[i][j-1]){
                    jumps[i].pb(all[i][j]);
                }
            }
        }
        reverse(jumps[i].begin(), jumps[i].end());
    }
    for(int i=0; i< n; i++)dist[i]=inf;
    dist[s]=0;
    st.push({0, s});
    while(st.size()){
        pair<int, int> nd = st.top();
        st.pop();
        if(mark[nd.S] || dist[nd.S]<nd.F)continue;
        mark[nd.S]=1;
        if(nd.S==t){
            cout << nd.F << '\n';
            return 0;
        }
        for(int jump : jumps[nd.S]){
            int cnt=1;
            for(int i=nd.S-jump; i>=0; i-=jump){
                if(nd.F+cnt<dist[i]){
                    dist[i]=nd.F+cnt;
                    st.push({dist[i], i});
                }
                cnt++;
                if(nd.F+cnt>=dist[t])break;
            }
            cnt=1;
            for(int i=nd.S+jump; i<n; i+=jump){
                if(nd.F+cnt<dist[i]){
                    dist[i]=nd.F+cnt;
                    st.push({dist[i], i});
                }
                cnt++;
                if(nd.F+cnt>=dist[t])break;
            }
        }
    }
    if(dist[t]==inf)cout << -1 << '\n';
    else cout << dist[t] << '\n';
}

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

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             for(int j=1; j<all[i].size(); j++){
      |                          ~^~~~~~~~~~~~~~
skyscraper.cpp:63:36: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |                 if(nd.F+cnt>=dist[t])break;
      |                              ~~~~~~^

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