Submission #109591

#TimeUsernameProblemLanguageResultExecution timeMemory
109591arman_ferdousJakarta Skyscrapers (APIO15_skyscraper)C++17
100 / 100
368 ms65892 KiB
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include <bits/stdc++.h> using namespace std; const int N = 30010; const int oo = 1e8; using ii = pair<int,int>; int n, m, st, ft; vector<int> f[N]; int dist[N]; vector<ii> g[N]; priority_queue<ii, vector<ii>, greater<ii> > q; bool has(int b, int p) { int lo = 0, hi = (int)f[b].size() - 1; while(lo <= hi) { int mid = (lo + hi) >> 1; if(f[b][mid] == p) return true; if(f[b][mid] < p) lo = mid+1; else hi = mid-1; } return false; } int main() { scanf("%d %d", &n, &m); for(int i = 0; i < m; ++i) { int b, p; scanf("%d %d", &b, &p); f[b].push_back(p); if(i == 0) st = b; else if(i == 1) ft = b; } for(int i = 0; i < n; ++i) { sort(f[i].begin(), f[i].end()); f[i].erase(unique(f[i].begin(),f[i].end()), f[i].end()); } for(int i = 0; i < n; ++i) { for(int p : f[i]) { for(int x = i + p, c = 1; x < n; x += p, ++c) { g[i].push_back({c, x}); if(has(x,p)) break; } for(int x = i - p, c = 1; x >= 0; x -= p, ++c) { g[i].push_back({c, x}); if(has(x,p)) break; } } } for(int i = 0; i < n; ++i) dist[i] = oo; q.push({0,st}); dist[st] = 0; while(!q.empty()) { auto U = q.top(); q.pop(); int cw = U.first, u = U.second; for(auto e : g[u]) { if(dist[e.second] > cw + e.first) { dist[e.second] = cw + e.first; q.push({cw + e.first, e.second}); } } } if(dist[ft] == oo) puts("-1"); else printf("%d\n", dist[ft]); return 0; }

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:29: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:31:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int b, p; scanf("%d %d", &b, &p);
             ~~~~~^~~~~~~~~~~~~~~~~
#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...