# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
185624 | dndhk | Jakarta Skyscrapers (APIO15_skyscraper) | C++14 | 4 ms | 668 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |