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 all(aa) aa.begin(), aa.end()
#define pb push_back
#define endl ("\n")
typedef long long ll;
using namespace std;
const int maxn = 2005, maxm = 2005;
int n, m, target;
bool vis[maxn][maxm];
vector<int> v[maxn];
ll d[maxn][maxm], sped;
queue<array<ll, 3>> q;
void pushq(ll u, ll s, ll dst){
if(u - s >= 0) q.push({u - s, s, dst+1});
if(u + s < n) q.push({u+s, s, dst+1});
}
int main(){
cin >> n >> m;
for(int i = 0; i < m; i++){
int b, p;
cin >> b >> p;
if(i == 0) sped = p;
if(i != 1) v[b].pb(p);
else target = b;
}
for(int i = 0; i < n; i++){
sort(all(v[i]));
v[i].resize(unique(all(v[i])) - v[i].begin());
}
pushq(0, sped, 0);
while(!q.empty()){
auto [u, s, dst] = q.front(); q.pop();
if(u == target) cout << dst << endl, exit(0);
if(vis[u][s]) continue;
vis[u][s] = 1;
d[u][s] = dst;
for(int sp : v[u])
pushq(u, sp, dst);
if(u - s >= 0) q.push({u - s, s, dst+1});
if(u + s < n) q.push({u+s, s, dst+1});
}
cout << -1 << endl;
}
Compilation message (stderr)
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:36:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
36 | auto [u, s, dst] = q.front(); q.pop();
| ^| # | 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... |