oj.uz

Submission #118414

# Submission time Handle Problem Language Result Execution time Memory
118414 2019-06-19T01:41:19 Z kig9981 None (JOI16_skating) C++17
0 / 100
 5 ms 4352 KB 
#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

int D[1000][1000][4], dist[1000][1000];
vector<string> F;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, M, x, y;
	priority_queue<tuple<int,int,int>> Q;
	cin>>N>>M;
	F.resize(N);
	for(int i=0;i<N;i++) cin>>F[i];
	for(int i=0;i<N;i++) {
		D[i][M-1][1]=M-1;
		for(int j=1;j<M;j++) D[i][j][0]=F[i][j-1]=='.' ? D[i][j-1][0]:j;
		for(int j=M-2;j>=0;j--) D[i][j][1]=F[i][j+1]=='.' ? D[i][j+1][1]:j;
	}
	for(int j=0;j<M;j++) {
		D[N-1][j][3]=N-1;
		for(int i=1;i<N;i++) D[i][j][2]=F[i-1][j]=='.' ? D[i-1][j][2]:i;
		for(int i=N-2;i>=0;i--) D[i][j][3]=F[i+1][j]=='.' ? D[i+1][j][3]:i;
	}
	cin>>x>>y;
	memset(dist,0x7f,sizeof(dist));
	dist[--x][--y]=0;
	Q.emplace(0,x,y);
	while(!Q.empty()) {
		auto[t,x,y]=Q.top();
		Q.pop();
		if(-t!=dist[x][y]) continue;
		for(int i=D[x][y][0];i<=D[x][y][1];i++) if(dist[x][i]>dist[x][y]+1+2*min(i-D[x][y][0],D[x][y][1]-i)) {
			dist[x][i]=dist[x][y]+1+2*min(i-D[x][y][0],D[x][y][1]-i);
			Q.emplace(-dist[x][i],x,i);
		}
		for(int i=D[x][y][2];i<=D[x][y][3];i++) if(dist[i][y]>dist[x][y]+1+2*min(i-D[x][y][2],D[x][y][3]-i)) {
			dist[i][y]=dist[x][y]+1+2*min(i-D[x][y][2],D[x][y][3]-i);
			Q.emplace(-dist[i][y],i,y);
		}
	}
	cin>>x>>y;
	cout<<(dist[--x][--y]==0x7f7f7f7f ? -1:dist[x][y])<<'\n';
	return 0;
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 65.0

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

Subtask #3
0 / 22.0

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