Submission #118414

#	Time	Username	Problem	Language	Result	Execution time	Memory
118414		kig9981	Dangerous Skating (JOI16_skating)	C++17	0 / 100	5 ms	4352 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;

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
• Subtask 2: 0 / 65
• Subtask 3: 0 / 22