제출 #867227

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
867227		1075508020060209tc	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	3 ms	2908 KiB

skyscraper

#pragma GCC optimize ("O3")
#include<bits/stdc++.h>
using namespace std;
//#define int long long
int n;int m;
//int dis[30100];
vector<int>e[30100];
set<int>st[30100];
map<pair<int,int>,int>vis;
map<pair<int,int>,int>dis;
int ar[30100];
int br[30100];
int frm[30100];
signed main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
cin>>n>>m;
for(int i=0;i<m;i++){
    cin>>ar[i]>>br[i];
    st[ar[i]].insert(br[i]);
//    e[ar[i]].push_back(br[i]);
}
for(int i=0;i<n;i++){
    for(auto it=st[i].begin();it!=st[i].end();it++){
        e[i].push_back(*it);
    }
    e[i].push_back(0);
}

dis[{ar[0],0}]=1;
deque<pair<int,int>>dq;
dq.push_back({ar[0],0});
while(dq.size()){
    int nw=dq.front().first;
    int nwd=dq.front().second;
    dq.pop_front();
    if(vis[{nw,nwd}]){continue;}
    vis[{nw,nwd}]=1;
    for(int i=0;i<e[nw].size();i++){
        int d=e[nw][i];
        if(vis[{nw,d}]){continue;}
        if(dis[{nw,d}]==0){
            dis[{nw,d}]=dis[{nw,nwd}];
            dq.push_front({nw,d});
            continue;
        }
        if(dis[{nw,d}]>dis[{nw,nwd}]){
            dis[{nw,d}]=dis[{nw,nwd}];
            dq.push_front({nw,d});
        }
    }
    if(nw+nwd<n){
        if(dis[{nw+nwd,nwd}]==0){
            dis[{nw+nwd,nwd}]=dis[{nw,nwd}]+1;
            dq.push_back({nw+nwd,nwd});
            continue;
        }
        if(dis[{nw+nwd,nwd}]>dis[{nw,nwd}]+1){
            dis[{nw+nwd,nwd}]=dis[{nw,nwd}]+1;
            dq.push_back({nw+nwd,nwd});
        }
    }
    if(nw+nwd>=0){
        if(dis[{nw-nwd,nwd}]==0){
            dis[{nw-nwd,nwd}]=dis[{nw,nwd}]+1;
            dq.push_back({nw-nwd,nwd});
            continue;
        }
        if(dis[{nw-nwd,nwd}]>dis[{nw,nwd}]+1){
            dis[{nw-nwd,nwd}]=dis[{nw,nwd}]+1;
            dq.push_back({nw-nwd,nwd});
        }
    }
}
cout<<dis[{ar[1],0}]-1;


}

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

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i=0;i<e[nw].size();i++){
      |                 ~^~~~~~~~~~~~~

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