oj.uz

답안 #199571

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
199571 2020-02-02T04:52:26 Z arnold518 Dangerous Skating (JOI16_skating) C++14
13 / 100
 1371 ms 262148 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];

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

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.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 5 ms 508 KB Output is correct
9 Correct 5 ms 632 KB Output is correct
10 Correct 5 ms 504 KB Output is correct

Subtask #2
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 5 ms 508 KB Output is correct
9 Correct 5 ms 632 KB Output is correct
10 Correct 5 ms 504 KB Output is correct
11 Runtime error 1371 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 5 ms 508 KB Output is correct
9 Correct 5 ms 632 KB Output is correct
10 Correct 5 ms 504 KB Output is correct
11 Runtime error 1371 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -