Submission #722407

#TimeUsernameProblemLanguageResultExecution timeMemory
722407n0sk1llJakarta Skyscrapers (APIO15_skyscraper)C++14
100 / 100
48 ms14160 KiB
#include <bits/stdc++.h> #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0) #define mp make_pair #define xx first #define yy second #define pb push_back #define pf push_front #define popb pop_back #define popf pop_front #define all(x) x.begin(),x.end() #define ff(i,a,b) for (int i = a; i < b; i++) #define fff(i,a,b) for (int i = a; i <= b; i++) #define bff(i,a,b) for (int i = b-1; i >= a; i--) #define bfff(i,a,b) for (int i = b; i >= a; i--) using namespace std; long double typedef ld; unsigned int typedef ui; long long int typedef li; pair<int,int> typedef pii; pair<li,li> typedef pli; pair<ld,ld> typedef pld; vector<vector<int>> typedef graph; unsigned long long int typedef ull; //const int mod = 998244353; //const int mod = 1000000007; //Note to self: Check for overflow bool vis[30003]; set<int> psi[30003]; vector<pii> g[30003]; int main() { FAST; int n,m; cin>>n>>m; set<pii> doges; int s,t; ff(i,0,m) { int b,p; cin>>b>>p; doges.insert({b,p}); if (i==0) s=b; if (i==1) t=b; } for (auto [b,p] : doges) psi[b].insert(-p); vector<bool> tempvis(n,0); ff(i,0,n) { for (auto __jmp : psi[i]) { int jmp=-__jmp; int tez=1; int tit=i; while (true) { int got=tit+jmp; if (got>=n) break; if (!tempvis[got] && !psi[got].empty()) g[i].pb({got,tez}),tempvis[got]=true; tit=got,tez++; if (psi[tit].count(__jmp)) break; } tez=1; tit=i; while (true) { int got=tit-jmp; if (got<0) break; if (!tempvis[got] && !psi[got].empty()) g[i].pb({got,tez}),tempvis[got]=true; tit=got,tez++; if (psi[tit].count(__jmp)) break; } } for (auto sta : g[i]) tempvis[sta.xx]=0; } priority_queue<pii,vector<pii>,greater<pii>> pq; pq.push({0,s}); while (!pq.empty()) { auto [d,p]=pq.top(); pq.pop(); if (vis[p]) continue; vis[p]=1; if (p==t) return cout<<d,0; for (auto [it,w] : g[p]) if (!vis[it]) pq.push({w+d,it}); } cout<<-1; } //Note to self: Check for overflow /* 5 3 0 2 1 1 4 1 */

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:58:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |     for (auto [b,p] : doges) psi[b].insert(-p);
      |               ^
skyscraper.cpp:98:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   98 |         auto [d,p]=pq.top(); pq.pop();
      |              ^
skyscraper.cpp:99:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   99 |         if (vis[p]) continue; vis[p]=1;
      |         ^~
skyscraper.cpp:99:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   99 |         if (vis[p]) continue; vis[p]=1;
      |                               ^~~
skyscraper.cpp:102:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |         for (auto [it,w] : g[p]) if (!vis[it]) pq.push({w+d,it});
      |                   ^
skyscraper.cpp:100:9: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
  100 |         if (p==t) return cout<<d,0;
      |         ^~
#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...