Submission #516208

#TimeUsernameProblemLanguageResultExecution timeMemory
516208DiriiJakarta Skyscrapers (APIO15_skyscraper)C++14
0 / 100
1 ms972 KiB
// #pragma GCC target("avx2") // #pragma GCC optimize("Ofast") // #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #define ll long long #define cll const ll #define lp(a, b, c) for(ll a = b; a <= c; ++a) #define lpd(a, b, c) for(ll a = b; a >= c; --a) #define vec(a) vector<a> #define pp(a, b) pair<a, b> #define EACHCASE lpd(cs, read(), 1) #define Fname "f" using namespace std; template <typename T> inline void Read(T &x){ x = 0; char c; ll dau = 1; while(!isdigit(c = getchar())) if(c == '-') dau = -1; do{ x = x * 10 + c - '0'; } while (isdigit(c = getchar())); x *= dau; } ll read(){ ll tmp; cin >> tmp; return tmp; } void giuncute(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } void OF(){ if(fopen(Fname".inp", "r")){ freopen(Fname".inp", "r", stdin); freopen(Fname".out", "w", stdout); } else if(fopen(Fname".in", "r")){ freopen(Fname".in", "r", stdin); freopen(Fname".out", "w", stdout); } } cll mxn = 3e4 + 5, _sqrt = 173; ll n, m, dp[mxn][_sqrt + 4], initu, initp, finalu, finalp; vec(ll) jump[mxn]; priority_queue<pp(ll, pp(ll, ll))> q; void prc(ll u, ll cu, ll step){ if(u + step < n && dp[u + step][step] > cu + 1){ dp[u + step][step] = cu + 1; q.push({-dp[u + step][step], {u + step, step}}); } if(u - step >= 0 && dp[u - step][step] > cu + 1){ dp[u - step][step] = cu + 1; q.push({-dp[u - step][step], {u - step, step}}); } if(u + step < n && dp[u + step][0] > cu + 1){ dp[u + step][0] = cu + 1; q.push({-dp[u + step][0], {u + step, 0}}); } if(u - step >= 0 && dp[u - step][0] > cu + 1){ dp[u - step][0] = cu + 1; q.push({-dp[u - step][0], {u - step, 0}}); } } int main(){ giuncute(); #ifndef ONLINE_JUDGE OF(); #endif cin >> n >> m; lp(i, 1, m){ static ll u, p; cin >> u >> p; if(i == 1) initu = u, initp = p; if(i == 2) finalu = u, finalp = p; jump[u].push_back(p); } lp(i, 0, n) lp(j, 0, _sqrt) dp[i][j] = 1e16; dp[initu][initp] = 0; if(initu + initp < n){ dp[initu + initp][initp] = 1; q.push({-1, {initu + initp, initp}}); } if(initu - initp >= 0){ dp[initu - initp][initp] = 1; q.push({-1, {initu - initp, initp}}); } ll ans = 1e16; while(q.size()){ ll cu = -q.top().first, u = q.top().second.first, step = q.top().second.second; q.pop(); if(cu != dp[u][step]) continue; if(u == finalu) ans = min(ans, cu); // maintain last step prc(u, cu, step); // change step for(ll i : jump[u]){ if(i <= _sqrt) prc(u, cu, i); else{ for(ll v = u + i, cnt = 1; v < n; v += i, ++cnt) if(dp[v][0] > cu + cnt){ dp[v][0] = cu + cnt; q.push({-dp[v][0], {v, 0}}); } for(ll v = u - i, cnt = 1; v >= 0; v -= i, ++cnt) if(dp[v][0] > cu + cnt){ dp[v][0] = cu + cnt; q.push({-dp[v][0], {v, 0}}); } } } } if(ans > 1e15) ans = -1; cout << ans; }

Compilation message (stderr)

skyscraper.cpp: In function 'void OF()':
skyscraper.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen(Fname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen(Fname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen(Fname".in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen(Fname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#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...