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>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define INF 1e9
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<pair<int,int> > vii;
int n,m;
vector<vi> ns;
bitset<30001> dp[30001],vis;
queue<pair<ii,int> > q;
void solve(int pos, int u, int d, int p){
if(pos<0 || pos>=n) return;
if(dp[pos][p]) return;
dp[pos][p]=true;
q.push(mp(mp(d+1,pos),p));
if(!vis[pos]){
for(int i:ns[pos]) q.push(mp(mp(d+1,pos),i));
vis[pos]=true;
}
}
int main(){
//printf("here\n");
scanf("%d%d",&n,&m);
ns.assign(n+2,vi());
int n1;
int nf;
for(int i=0;i<m;i++){
int x,y;
scanf("%d%d",&x,&y);
if(!i) n1=x;
if(i==1) nf=x;
ns[x].pb(y);
//jm[i]=y;
}
//for(int i=0;i<n;i++) printf("%d ", dis[n1][i]); printf("\n");
for(int i:ns[n1]){
dp[n1][i]=true;
q.push(mp(mp(0,n1),i));
}
while(!q.empty()){
int u=q.front().fi.se;
int d=q.front().fi.fi;
int p=q.front().se;
q.pop();
if(u==nf){
printf("%d\n", d);
return 0;
}
solve(u+p,u,d,p);
//printf("%d %d\n",u,p);
solve(u-p,u,d,p);
}
//printf("%d %d\n", n1,nf);
printf("-1\n");
return 0;
}
Compilation message (stderr)
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:29: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:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&x,&y);
~~~~~^~~~~~~~~~~~~~
skyscraper.cpp:42:17: warning: 'n1' may be used uninitialized in this function [-Wmaybe-uninitialized]
for(int i:ns[n1]){
^
skyscraper.cpp:51:3: warning: 'nf' may be used uninitialized in this function [-Wmaybe-uninitialized]
if(u==nf){
^~
# | 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... |