제출 #504065

#제출 시각아이디문제언어결과실행 시간메모리
504065FronPawJakarta Skyscrapers (APIO15_skyscraper)C++14
100 / 100
267 ms63100 KiB
#include <bits/stdc++.h> #define mod 1000000007 // https://www.youtube.com/watch?v=t5GDacP_2pQ using namespace std; ifstream in ("film.in"); ofstream out ("film.out"); int pow (int a, int b) { int rez = 1; while (b) { if (b&1) rez = (rez * a) % mod; a = (a * a) % mod; b>>=1; } return rez; } int n, m; set <int> b[30001]; vector <pair <int, int> > v[30001]; int ans[30001]; void dij (int start) { for (int i = 0; i<=30000; ++i) ans[i] = 1<<30; ans[start] = 0; set <pair<int, int> > q; q.insert({0, start}); while (!q.empty()) { int nod = (*q.begin()).second; q.erase(q.begin()); int cost = ans[nod]; for (auto vecin:v[nod]) if (cost + vecin.second < ans[vecin.first]) { if (ans[vecin.first] != 1<<30) q.erase(q.find({ans[vecin.first], vecin.first})); q.insert({cost + vecin.second, vecin.first}); ans[vecin.first] = cost + vecin.second; } } } void solve () { int first, last; cin >> n >> m; for (int i = 1; i<=m; ++i) { int a, c; cin >> a >> c; if (i == 1) first = a; else if (i == 2) last = a; b[a].insert(c); } for (int i = 0; i<n; ++i) for (auto pp:b[i]) { int place = i; place -= pp; int move1 = 1; while (place >= 0) { v[i].push_back({place, move1}); if (b[place].count(pp)) break; move1++; place -= pp; } place = i + pp; move1 = 1; while (place < n) { v[i].push_back({place, move1}); if (b[place].count(pp)) break; move1++; place += pp; } } dij(first); if (ans[last] == 1<<30) cout << -1 << ' '; else cout << ans[last] << ' '; return; } main () { //ios_base::sync_with_stdio(false); //cin.tie(NULL); int t = 1; //cin >> t; while (t--) solve(); }

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

skyscraper.cpp:92:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   92 | main ()
      | ^~~~
skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:86:17: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
   86 |     if (ans[last] == 1<<30)
      |         ~~~~~~~~^
skyscraper.cpp:85:8: warning: 'first' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |     dij(first);
      |     ~~~^~~~~~~
#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...