oj.uz

Submission #313180

# Submission time Handle Problem Language Result Execution time Memory
313180 2020-10-15T12:25:49 Z AngelKnows Sky Walking (IOI19_walk) C++14
0 / 100
 20 ms 4352 KB 
#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

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) {
      |                               ~~~~^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 3064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 3064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4352 KB Output isn't correct
2 Halted 0 ms 0 KB -