Submission #72385

#	Time	Username	Problem	Language	Result	Execution time	Memory
72385		The quick brown fox jumps over the lazy dog (#118)	Aquatic Labyrinth (FXCUP3_aqua)	C++17	100 / 100	985 ms	72672 KiB

aqua

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;

const ll N = 905, inf = 1e18;
const ll dx[5] = {0, 1, -1, 0, 0}, dy[5] = {0, 0, 0, 1, -1};
const ll LL = 4, RR = 3, DD = 1, UU = 2;

char ipt[N][N];

ll n, dis[N][N][5], ver[N][N], hor[N][N];
ll l[N][N], r[N][N], d[N][N], u[N][N];

pll s, e;

priority_queue<pair<ll, pair<pll, ll> > > pq;

bool valid (ll X, ll Y) {
	return (1 <= X && X <= n && 1 <= Y && Y <= n && ipt[X][Y] != 'W');
}

ll sq (ll X) {
	return X*X;
}

int main()
{
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++) {
		scanf("%s",ipt[i]+1);
		for(ll j=1;j<=n;j++) {
			if(ipt[i][j] == 'M') {
				s = {i, j};
				ipt[i][j] = '.';
			}
			if(ipt[i][j] == 'H') {
				e = {i, j};
				ipt[i][j] = '.';
			}
			ver[i][j] = ver[i-1][j] + (ipt[i][j] == 'W');
			hor[i][j] = hor[i][j-1] + (ipt[i][j] == 'W');
			for(ll k=0;k<5;k++) {
				dis[i][j][k] = inf;
			}
		}
	}
	for(ll i=1;i<=n;i++) {
		for(ll j=1;j<=n;j++) {
			if(ipt[i][j] == 'W' && ipt[i][j-1] != 'W') l[i][j] = j-1;
			else l[i][j] = l[i][j-1];
			if(ipt[i][j] == 'W' && ipt[i-1][j] != 'W') u[i][j] = i-1;
			else u[i][j] = u[i-1][j];
		}
	}
	for(ll i=n;i>=1;i--) {
		for(ll j=n;j>=1;j--) {
			if(ipt[i][j] == 'W' && ipt[i][j+1] != 'W') r[i][j] = j+1;
			else r[i][j] = r[i][j+1];
			if(ipt[i][j] == 'W' && ipt[i+1][j] != 'W') d[i][j] = i+1;
			else d[i][j] = d[i+1][j];
		}
	}
	dis[s.X][s.Y][0] = 0;
	pq.push({0, {{s.X, s.Y}, 0}});
	while(!pq.empty()) {
		auto C = pq.top(); pq.pop();
		ll V = -C.X, X = C.Y.X.X, Y = C.Y.X.Y, D = C.Y.Y;
		if(dis[X][Y][D] != V) continue;
		ll NX, NY, ND, NV;
		NX = X, NY = l[X][Y], ND = LL, NV = V + sq(hor[NX][NY] - hor[X][Y]);
		if(valid(NX, NY) && dis[NX][NY][ND] > NV) {
			dis[NX][NY][ND] = NV;
			pq.push({-NV, {{NX, NY}, ND}});
		}
		NX = X, NY = r[X][Y], ND = RR, NV = V + sq(hor[NX][NY] - hor[X][Y]);
		if(valid(NX, NY) && dis[NX][NY][ND] > NV) {
			dis[NX][NY][ND] = NV;
			pq.push({-NV, {{NX, NY}, ND}});
		}
		NX = d[X][Y], NY = Y, ND = DD, NV = V + sq(ver[NX][NY] - ver[X][Y]);
		if(valid(NX, NY) && dis[NX][NY][ND] > NV) {
			dis[NX][NY][ND] = NV;
			pq.push({-NV, {{NX, NY}, ND}});
		}
		NX = u[X][Y], NY = Y, ND = UU, NV = V + sq(ver[NX][NY] - ver[X][Y]);
		if(valid(NX, NY) && dis[NX][NY][ND] > NV) {
			dis[NX][NY][ND] = NV;
			pq.push({-NV, {{NX, NY}, ND}});
		}
		NX = X+dx[D], NY = Y+dy[D], ND = D, NV = V;
		if(valid(NX, NY) && dis[NX][NY][ND] > NV) {
			dis[NX][NY][ND] = NV;
			pq.push({-NV, {{NX, NY}, ND}});
		}
	}
	ll ans = inf;
	for(ll i=0;i<5;i++) {
		ans = min(ans, dis[e.X][e.Y][i]);
	}
	printf("%lld\n",ans == inf ? -1 : ans);
}

Compilation message (stderr)

aqua.cpp: In function 'int main()':
aqua.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
aqua.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",ipt[i]+1);
   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 36 / 36
• Subtask 2: 64 / 64