Submission #199574

#	Time	Username	Problem	Language	Result	Execution time	Memory
199574		arnold518	Dangerous Skating (JOI16_skating)	C++14	78 / 100	2393 ms	262148 KiB

skating

#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];

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;

	priority_queue<Queue> PQ;
	PQ.push({SY, SX, 0, 0});
	PQ.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, k;
			l=L[T.y][T.x]+1, r=T.x-1, k=0;
			for(i=1; l<=r; i++)
			{
				if(k==0)
				{
					if(dist[T.y][l][1]>T.d+i) PQ.push({T.y, l, 1, T.d+i});
					k=1; l++;
				}
				else
				{
					if(dist[T.y][r][1]>T.d+i) PQ.push({T.y, r, 1, T.d+i});
					r--; k=0;
				}
			}
			l=T.x+1, r=R[T.y][T.x]-1, k=0;
			for(i=1; l<=r; i++)
			{
				if(k==1)
				{
					if(dist[T.y][l][1]>T.d+i) PQ.push({T.y, l, 1, T.d+i});
					l++; k=0;
				}
				else
				{
					if(dist[T.y][r][1]>T.d+i) PQ.push({T.y, r, 1, T.d+i});
					r--; k=1;
				}
			}
			if(dist[T.y][T.x][1]>T.d) PQ.push({T.y, T.x, 1, T.d});
		}
		else
		{
			int l, r, k;
			l=U[T.y][T.x]+1, r=T.y-1, k=0;
			for(i=1; l<=r; i++)
			{
				if(k==0)
				{
					if(dist[l][T.x][0]>T.d+i) PQ.push({l, T.x, 0, T.d+i});
					l++; k=1;
				}
				else
				{
					if(dist[r][T.x][0]>T.d+i) PQ.push({r, T.x, 0, T.d+i});
					r--; k=0;
				}
			}
			l=T.y+1, r=D[T.y][T.x]-1, k=0;
			for(i=1; l<=r; i++)
			{
				if(k==1)
				{
					if(dist[l][T.x][0]>T.d+i) PQ.push({l, T.x, 0, T.d+i});
					l++; k=0;
				}
				else
				{
					if(dist[r][T.x][0]>T.d+i) PQ.push({r, T.x, 0, T.d+i});
					r--; k=1;
				}
			}
			if(dist[T.y][T.x][0]>T.d) PQ.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 (stderr)

skating.cpp: In function 'int main()':
skating.cpp:26: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:27: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:28: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: 13 / 13
• Subtask 2: 65 / 65
• Subtask 3: 0 / 22