제출 #392982

#제출 시각아이디문제언어결과실행 시간메모리
392982giorgikobJakarta Skyscrapers (APIO15_skyscraper)C++14
36 / 100
1087 ms3248 KiB
#include<bits/stdc++.h> #define ll long long #define ff first #define ss second #define pb push_back using namespace std; const int N = 3e4+5, mod = 1e9+7, sq = 500; int n,m; set<pair<int,int>>s; int D[N]; int X[N],P[N]; int F[N]; vector<int>V[N]; inline void test_case(){ cin>>n>>m; for(int i=1;i<=m;i++){ cin>>X[i]>>P[i]; X[i]++; V[X[i]].push_back(i); } for(int i=1;i<=m;i++){ if(i>1){ D[i] = 1e9; //s.insert({1e9,i}); } } D[1] = 0; F[X[1]] = 1; s.insert({0,1}); while(s.size()){ pair<int,int> p = *(s.begin()); s.erase(s.begin()); int i = p.second; int dist = p.first; F[X[i]] = 1; if(i==2){ if(D[2]==1e9)D[2]=-1; cout<<D[2]<<endl; return ; } for(int j=X[i];j<=n;j+=P[i]){ if(F[j] && j != X[i]) continue; for(int k=0;k<V[j].size();k++){ int to = V[j][k]; if(D[to] > dist + (j-X[i])/P[i] || D[to]==1e9){ if(D[to]!=1e9) s.erase({D[to],to}); D[to] = dist + (j-X[i])/P[i]; s.insert({D[to],to}); } } } for(int j=X[i]-P[i];j>=1;j-=P[i]){ if(F[j]) continue; for(int k=0;k<V[j].size();k++){ int to = V[j][k]; if(D[to] > dist + (X[i]-j)/P[i] || D[to] == 1e9){ if(D[to]!=1e9) s.erase({D[to],to}); D[to] = dist + (X[i]-j)/P[i]; s.insert({D[to],to}); } } } } if(D[2]==1e9) D[2] = -1; cout<<D[2]<<endl; } main(){ ios::sync_with_stdio(0); int T = 1; //cin >> T; while(T--){ test_case(); } }

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

skyscraper.cpp: In function 'void test_case()':
skyscraper.cpp:54:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    for(int k=0;k<V[j].size();k++){
      |                ~^~~~~~~~~~~~
skyscraper.cpp:69:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |    for(int k=0;k<V[j].size();k++){
      |                ~^~~~~~~~~~~~
skyscraper.cpp: At global scope:
skyscraper.cpp:89:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   89 |  main(){
      |       ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...