Submission #115648

#TimeUsernameProblemLanguageResultExecution timeMemory
115648imyujinJakarta Skyscrapers (APIO15_skyscraper)C++14
10 / 100
3 ms1152 KiB
#include<stdio.h> #include<vector> #include<queue> #include<algorithm> using namespace std; #define MAXN 30005 #define MAXM 30005 #define LINF 8100000000ll #define fi first #define se second typedef pair<int, int> pi; long long dp[MAXN]; int B[MAXM], P[MAXM]; vector<int> d[MAXN]; priority_queue<pi, vector<pi>, greater<pi> > pq; int main(){ int N, M; scanf("%d%d", &N, &M); for(int i=0; i<M; i++) scanf("%d%d", B+i, P+i); for(int i=0; i<M; i++) d[B[i]].push_back(P[i]); for(int i=0; i<N; i++){ sort(d[i].begin(), d[i].end()); unique(d[i].begin(), d[i].end()); } pq.push(make_pair(0, B[0])); for(int i=0; i<N; i++) dp[i]=LINF; dp[B[0]]=0; while(!pq.empty()){ pi t=pq.top(); pq.pop(); if(t.se==B[1]){ printf("%lld", dp[B[1]]); return 0; } for(int j=0; j<d[t.se].size(); j++){ int l=t.se+d[t.se][j]; for(int k=1; l<N; k++, l+=d[t.se][j]){ if(t.fi+k<dp[l]){ dp[l]=t.fi+k; pq.push(make_pair(t.fi+k, l)); } if(lower_bound(d[l].begin(), d[l].end(), d[t.se][j])!=d[l].end()) break; } l=t.se-d[t.se][j]; for(int k=1; l>=0; k++, l-=d[t.se][j]){ if(t.fi+k<dp[l]){ dp[l]=t.fi+k; pq.push(make_pair(t.fi+k, l)); } if(lower_bound(d[l].begin(), d[l].end(), d[t.se][j])!=d[l].end()) break; } } } printf("-1"); return 0; }

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:43:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<d[t.se].size(); j++){
                ~^~~~~~~~~~~~~~~
skyscraper.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:25:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<M; i++) scanf("%d%d", B+i, P+i);
                         ~~~~~^~~~~~~~~~~~~~~~~~
#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...