Submission #118417

#	Time	Username	Problem	Language	Result	Execution time	Memory
118417		kig9981	Dangerous Skating (JOI16_skating)	C++17	100 / 100	417 ms	23668 KiB

skating

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

const int dx[]={-1,1,0,0}, dy[]={0,0,-1,1};
int N, M, D[1000][1000][4], dist[1000][1000];
vector<string> F;

bool valid_coord(int x, int y)
{
	return 0<=x && x<N && 0<=y && y<M && F[x][y]=='.';
}

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 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 k=0;k<4;k++) if(valid_coord(x+dx[k],y+dy[k]) && dist[x+dx[k]][y+dy[k]]>dist[x][y]+2) {
			dist[x+dx[k]][y+dy[k]]=dist[x][y]+2;
			Q.emplace(-dist[x+dx[k]][y+dy[k]],x+dx[k],y+dy[k]);
		}
		if(dist[x][D[x][y][0]]>dist[x][y]+1) {
			dist[x][D[x][y][0]]=dist[x][y]+1;
			Q.emplace(-dist[x][D[x][y][0]],x,D[x][y][0]);
		}
		if(dist[x][D[x][y][1]]>dist[x][y]+1) {
			dist[x][D[x][y][1]]=dist[x][y]+1;
			Q.emplace(-dist[x][D[x][y][1]],x,D[x][y][1]);
		}
		if(dist[D[x][y][2]][y]>dist[x][y]+1) {
			dist[D[x][y][2]][y]=dist[x][y]+1;
			Q.emplace(-dist[D[x][y][2]][y],D[x][y][2],y);
		}
		if(dist[D[x][y][3]][y]>dist[x][y]+1) {
			dist[D[x][y][3]][y]=dist[x][y]+1;
			Q.emplace(-dist[D[x][y][3]][y],D[x][y][3],y);
		}
	}
	cin>>x>>y;
	cout<<(dist[--x][--y]==0x7f7f7f7f ? -1:dist[x][y])<<'\n';
	return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 65 / 65
• Subtask 3: 22 / 22