Submission #72875

#	Time	Username	Problem	Language	Result	Execution time	Memory
72875		ainta	Aquatic Labyrinth (FXCUP3_aqua)	C++17	100 / 100	1255 ms	265072 KiB

aqua

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define pli pair<long long,int>
using namespace std;
int n, Num[910][910], NX[910][910], NY[910][910], BX[910], EX[910], BY[910], EY[910];
int L[3010000];
long long D[3010000];
char p[910][910];
priority_queue<pli>PQ;
vector<int>E[3010000], LL[3010000];
void Add_Edge(int a, int b, int d) {
	E[a].push_back(b);
	LL[a].push_back(d*d);
}
void Put(int a, long long d) {
	if (D[a] <= d)return;
	D[a] = d;
	PQ.push({ -d,a });
}
int main() {
	//freopen("input.txt", "r", stdin);
	int i, j, sx, sy, cnt = 0, ex, ey;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%s", p[i]+1);
		for (j = 1; j <= n; j++){
			if (p[i][j] == 'M') {
				sx = i, sy = j;
				p[i][j] = '.';
			}
			if (p[i][j] == 'H') {
				ex = i, ey = j;
				p[i][j] = '.';
			}
			if (p[i][j] == '.') {
				cnt++;
				Num[i][j] = cnt;
			}
		}
	}
	for (i = 1; i <= n; i++) {
		BX[i] = cnt + 1;
		int c = 0, cp = 0;
		for (j = 1; j <= n; j++) {
			if (p[i][j] == '.') {
				if (p[i][j - 1] != '.')cnt++;
				if (c) {
					cp = c;
					c = 0;
					L[cnt] = cp;
				}
				NX[i][j] = cnt;
			}
			if (p[i][j] == 'W') {
				c++;
			}
		}
		EX[i] = cnt;
	}
	for (i = 1; i <= n; i++) {
		BY[i] = cnt + 1;
		int c = 0, cp = 0;
		for (j = 1; j <= n; j++) {
			if (p[j][i] == '.') {
				if (p[j - 1][i] != '.')cnt++;
				if (c) {
					cp = c;
					c = 0;
					L[cnt] = cp;
				}
				NY[j][i] = cnt;
			}
			if (p[j][i] == 'W') {
				c++;
			}
		}
		EY[i] = cnt;
	}
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			Add_Edge(NX[i][j], Num[i][j], 0);
			Add_Edge(NY[i][j], Num[i][j], 0);
			if (NX[i][j] != BX[i]) {
				Add_Edge(Num[i][j], NX[i][j] - 1, L[NX[i][j]]);
			}
			if (NX[i][j] != EX[i]) {
				Add_Edge(Num[i][j], NX[i][j] + 1, L[NX[i][j] + 1]);
			}
			if (NY[i][j] != BY[j]) {
				Add_Edge(Num[i][j], NY[i][j] - 1, L[NY[i][j]]);
			}
			if (NY[i][j] != EY[j]) {
				Add_Edge(Num[i][j], NY[i][j] + 1, L[NY[i][j] + 1]);
			}
		}
	}
	for (i = 1; i <= cnt; i++)D[i] = 1e18;
	Put(Num[sx][sy], 0);
	while (!PQ.empty()) {
		pli tp = PQ.top();
		PQ.pop();
		int x = tp.second;
		if (D[x] != -tp.first)continue;
		for (i = 0; i < E[x].size(); i++) {
			Put(E[x][i], D[x] + LL[x][i]);
		}
	}
	long long res = D[Num[ex][ey]];
	if (res > 8e16)res = -1;
	printf("%lld\n", res);
}

Compilation message (stderr)

aqua.cpp: In function 'int main()':
aqua.cpp:106:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (i = 0; i < E[x].size(); i++) {
               ~~^~~~~~~~~~~~~
aqua.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
aqua.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", p[i]+1);
   ~~~~~^~~~~~~~~~~~~~
aqua.cpp:100:5: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
  Put(Num[sx][sy], 0);
  ~~~^~~~~~~~~~~~~~~~
aqua.cpp:100:5: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
aqua.cpp:110:30: warning: 'ey' may be used uninitialized in this function [-Wmaybe-uninitialized]
  long long res = D[Num[ex][ey]];
                    ~~~~~~~~~~^
aqua.cpp:110:30: warning: 'ex' may be used uninitialized in this function [-Wmaybe-uninitialized]

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