Submission #554685

#TimeUsernameProblemLanguageResultExecution timeMemory
554685kwongwengJakarta Skyscrapers (APIO15_skyscraper)C++17
57 / 100
1089 ms3668 KiB
/* Solution for APIO 2015 - Skyscrapper Tags : */ #include <bits/stdc++.h> using namespace std; #pragma GCC target ("avx2") #pragma GCC optimization ("Ofast") #pragma GCC optimization ("unroll-loops") typedef long long ll; typedef vector<int> vi; typedef pair<int, int> ii; typedef vector<ii> vii; typedef long double ld; typedef pair<ll, ll> pll; #define FOR(i, a, b) for(int i = a; i < b; i++) #define ROF(i, a, b) for(int i = a; i >= b; i--) #define ms memset #define pb push_back #define fi first #define se second ll MOD = 1000000007; ll power(ll base, ll n){ if (n == 0) return 1; if (n == 1) return base; ll halfn = power(base, n/2); if (n % 2 == 0) return (halfn * halfn) % MOD; return (((halfn * halfn) % MOD) * base) % MOD; } ll inverse(ll n){ return power(n, MOD-2); } ll add(ll a, ll b){ return (a+b) % MOD; } ll mul(ll a, ll b){ a %= MOD; return (a*b) % MOD; } ll gcd(ll a, ll b){ if (a == 1) return 1; if (a == 0) return b; return gcd(b%a, a); } void solve(){ // O(nm * log m) dijkstra's algo int n, m; cin >> n>> m; vi doge[n]; int dest; int start; FOR(i,0,m){ int b, p; cin >> b >> p; doge[b].pb(p); if (i==0) start = b; if (i==1) dest = b; } vi dist(n,MOD); dist[start] = 0; set<ii> st; st.insert({dist[start], start}); while (!st.empty()){ ii node = *st.begin(); st.erase(node); int u = node.se; for (int p : doge[u]){ int cur = u+p; int cnt = 1; while (cur<n){ if (!doge[cur].empty()){ if (dist[cur] <= dist[u] + cnt){ cur += p; cnt++; continue; } if (dist[cur] != MOD){ st.erase({dist[cur], cur}); } dist[cur] = dist[u] + cnt; st.insert({dist[cur], cur}); } cur += p; cnt++; } cur = u-p; cnt = 1; while (cur >= 0){ if (!doge[cur].empty()){ if (dist[cur] <= dist[u] + cnt){ cur -= p; cnt++; continue; } if (dist[cur] != MOD){ st.erase({dist[cur], cur}); } dist[cur] = dist[u] + cnt; st.insert({dist[cur], cur}); } cur -= p; cnt++; } } } if (dist[dest] == MOD){ cout << -1; return; } cout << dist[dest]; } int main() { ios::sync_with_stdio(false); int TC = 1; //cin >> TC; FOR(i, 1, TC+1){ //cout << "Case #" << i << ": "; solve(); } }

Compilation message (stderr)

skyscraper.cpp:10: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   10 | #pragma GCC optimization ("Ofast")
      | 
skyscraper.cpp:11: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   11 | #pragma GCC optimization ("unroll-loops")
      | 
skyscraper.cpp: In function 'void solve()':
skyscraper.cpp:67:15: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |     dist[start] = 0;
      |               ^
skyscraper.cpp:107:18: warning: 'dest' may be used uninitialized in this function [-Wmaybe-uninitialized]
  107 |     if (dist[dest] == MOD){
      |                  ^
#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...