oj.uz

Submission #199587

# Submission time Handle Problem Language Result Execution time Memory
199587 2020-02-02T05:54:13 Z arnold518 None (JOI16_skating) C++14
0 / 100
 5 ms 504 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1000;
const int INF = 987654321;

struct Queue
{
	int y, x, p, d;
	bool operator < (const Queue &p) const { return d>p.d; }
};

int N, M, SY, SX, EY, EX;
char S[MAXN+10][MAXN+10];
int dist[MAXN+10][MAXN+10][2];
int U[MAXN+10][MAXN+10], D[MAXN+10][MAXN+10], L[MAXN+10][MAXN+10], R[MAXN+10][MAXN+10];

priority_queue<Queue> PQ;
void push(int y, int x, int p, int d)
{
	if(dist[y][x][p]>d) PQ.push({y, x, p, d}), dist[y][x][p]=d;
}

int main()
{
	int i, j;

	scanf("%d%d", &N, &M);
	for(i=1; i<=N; i++) scanf("%s", S[i]+1);
	scanf("%d%d%d%d", &SY, &SX, &EY, &EX);

	for(i=1; i<=N; i++) for(j=1; j<=M; j++)
	{
		if(S[i][j]=='#') U[i][j]=i, L[i][j]=j;
		else U[i][j]=U[i-1][j], L[i][j]=L[i][j-1];
	}
	for(i=N; i>=1; i--) for(j=M; j>=1; j--)
	{
		if(S[i][j]=='#') D[i][j]=i, R[i][j]=j;
		else D[i][j]=D[i+1][j], R[i][j]=R[i][j+1];
	}

	for(i=1; i<=N; i++) for(j=1; j<=M; j++) dist[i][j][0]=dist[i][j][1]=INF;

	push(SY, SX, 0, 0);
	push(SY, SX, 1, 0);
	while(!PQ.empty())
	{
		Queue T=PQ.top(); PQ.pop();
		if(dist[T.y][T.x][T.p]<T.d) continue;
		dist[T.y][T.x][T.p]=T.d;

		if(T.p==0)
		{
			int l, r;
			l=L[T.y][T.x]+1, r=R[T.y][T.x]-1;
			push(T.y, l, 0, T.d+1);
			push(T.y, r, 0, T.d+1);
			if(l<=T.x-1) push(T.y, T.x-1, 0, T.d+2);
			if(T.x+1<=r) push(T.y, T.x+1, 0, T.d+2);
			push(T.y, T.x, 1, T.d);
		}
		else
		{
			int l, r;
			l=U[T.y][T.x]+1, r=D[T.y][T.x]-1;
			push(l, T.x, 1, T.d+1);
			push(r, T.x, 1, T.d+1);
			if(l<=T.y-1) push(T.y, T.x-1, 1, T.d+2);
			if(T.y+1<=r) push(T.y, T.x+1, 1, T.d+2);
			push(T.y, T.x, 0, T.d);
		}
	}
	int ans=min(dist[EY][EX][1], dist[EY][EX][0]);
	if(ans==INF) printf("-1\n");
	else printf("%d\n", ans);
}

Compilation message

skating.cpp: In function 'int main()':
skating.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
skating.cpp:33:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%s", S[i]+1);
                      ~~~~~^~~~~~~~~~~~~~
skating.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &SY, &SX, &EY, &EX);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

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

Subtask #2
0 / 65.0

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

Subtask #3
0 / 22.0

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