Submission #185624

#TimeUsernameProblemLanguageResultExecution timeMemory
185624dndhkJakarta Skyscrapers (APIO15_skyscraper)C++14
0 / 100
4 ms668 KiB
#include <bits/stdc++.h> #define pb push_back using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAX_N = 2000; const int INF = 10000000; int dp[MAX_N+1][MAX_N+1]; int N, M; vector<int> gp[MAX_N+1]; int s, e, d; bool chk[MAX_N+1]; deque<pii> dq; void check(int x, int y){ for(int i : gp[x]){ if(dp[x][i]>y){ dp[x][i] = y; dq.pb({x, i}); } } } int main(){ scanf("%d%d", &N, &M); for(int i=0; i<M; i++){ int a, b; scanf("%d%d", &a, &b); a++; gp[a].pb(b); if(i==0){ s = a; d = b; }else if(i==1){ e = a; } } for(int i=1; i<=N; i++){ for(int j=1; j<=N; j++){ dp[i][j] = INF; } } dq.pb({s, d}); dp[s][d] = 0; while(1){ pii now = dq.front(); dq.pop_front(); if(!chk[now.first]){ if(now.first==e){ printf("%d", dp[now.first][now.second]); return 0; } check(now.first, dp[now.first][now.second]); } if(now.first+now.second<=N){ if(dp[now.first+now.second][now.second]>dp[now.first][now.second]+1){ dp[now.first+now.second][now.second] = dp[now.first][now.second] + 1; dq.pb({now.first+now.second, now.second}); } } if(now.first-now.second>=1){ if(dp[now.first-now.second][now.second]>dp[now.first][now.second]+1){ dp[now.first-now.second][now.second] = dp[now.first][now.second] + 1; dq.pb({now.first-now.second, now.second}); } } } printf("-1"); return 0; }

Compilation message (stderr)

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