Submission #313180

#TimeUsernameProblemLanguageResultExecution timeMemory
313180AngelKnowsSky Walking (IOI19_walk)C++14
0 / 100
20 ms4352 KiB
#include "walk.h" #include <bits/stdc++.h> #include <cstdio> #include <cassert> using namespace std; #define FOR(i,n) for (int i=1;i<=n;i++) #define REP(i,a,b) for (int i=a;i<=b;i++) #define pb push_back #define fi first #define se second #define pi pair<int,int> #define mp make_pair typedef long long ll; const int inf=0x3f3f3f3f; const ll linf=1e18; const int N=1000+1; const double eps=1e-5; const int mo=1e9+7; int n,m,s,g; int xx[N],h[N]; int yy[N]; struct edge { int l,r; ll y; } e[N]; bool a[N][N]; int d[N][N]; struct point { int x,y; }; queue<point> q; bool ok_l[N][N],ok_r[N][N]; bool ok(int x,int y) { if (x<0||y<0) return 0; return 1; } void bfs() { d[xx[s]][0]=0; q.push(point{xx[s],0}); while (!q.empty()) { int x=q.front().x,y=q.front().y; q.pop(); REP(i,-1,1) REP(j,-1,1) if (i==0&&j||i&&j==0) { if (i==-1&&!ok_l[x][y]) continue; if (i==1&&!ok_r[x][y]) continue; if (ok(x+i,y+j)&&a[x+i][y+j]&&d[x+i][y+j]==inf) { d[x+i][y+j]=d[x][y]+1; //cout<<x<<" "<<y<<" "<<d[x][y]<<endl; q.push(point{x+i,y+j}); } } } } long long min_distance(std::vector<int> X, std::vector<int> H, std::vector<int> L, std::vector<int> R, std::vector<int> Y, int ss, int gg) { s=ss+1; g=gg+1; n=X.size(),m=Y.size(); FOR(i,n) xx[i]=X[i-1],h[i]=H[i-1]; FOR(i,m) e[i].l=L[i-1]+1,e[i].r=R[i-1]+1,e[i].y=Y[i-1]; FOR(i,n) { int hh=h[i]; REP(j,0,hh) a[xx[i]][j]=1; } FOR(i,m) { int l=e[i].l,r=e[i].r,y=e[i].y; REP(j,xx[l],xx[r]) a[j][y]=1; REP(j,xx[l],xx[r]-1) ok_r[j][y]=1; REP(j,xx[l]+1,xx[r]) ok_l[j][y]=1; } memset(d,0x3f,sizeof (d)); bfs(); ll ans=d[xx[g]][0]; if (ans>10000) ans=-1; return ans; }

Compilation message (stderr)

walk.cpp: In function 'void bfs()':
walk.cpp:47:35: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   47 |   REP(i,-1,1) REP(j,-1,1) if (i==0&&j||i&&j==0) {
      |                               ~~~~^~~
#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...