Submission #72243

#	Time	Username	Problem	Language	Result	Execution time	Memory
72243		이시대의진정한망겜스타투 (#118)	Aquatic Labyrinth (FXCUP3_aqua)	C++17	100 / 100	1418 ms	260216 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);
}


/*#include<cstdio>
#include<algorithm>
#include<vector>
#define N_ 303000
#define M_ 1010000
#define INF 99999999
using namespace std;
int n;
struct Edge {
	int b, e, f;
};
class MaxFlow {
public:
	Edge E[M_ * 2];
	vector<int>G[N_];
	int Level[N_], Q[N_], PV[N_], source, sink, n, flow, EC;
	void init(int N, int S, int T) {
		n = N, flow = EC = 0;
		source = S, sink = T;
		for (int i = 0; i <= N; i++)G[i].clear();
	}
	void Add_Edge(int a, int b, int f) {
		G[a].push_back(EC);
		G[b].push_back(EC + 1);
		E[EC++] = { a,b,f};
		E[EC++] = { b,a,0};
	}
	bool GetLevel() {
		int i;
		for (i = 1; i <= n; i++)Level[i] = -1;
		int head = 0, tail = 0;
		Q[++tail] = source, Level[source] = 0;
		while (head < tail) {
			int x = Q[++head];
			for (auto &y : G[x]) {
				if (E[y].f && Level[E[y].e] == -1) {
					Q[++tail] = E[y].e;
					Level[E[y].e] = Level[x] + 1;
				}
			}
		}
		return Level[sink] != -1;
	}
	int BlockFlow(int a, int f) {
		if (a == sink)return f;
		for (int &i = PV[a]; i >= 0; i--) {
			int x = G[a][i];
			if (E[x].f && Level[E[x].e] == Level[a] + 1) {
				int t = BlockFlow(E[x].e, min(f, E[x].f));
				if (t) {
					E[x].f -= t;
					E[x ^ 1].f += t;
					return t;
				}
			}
		}
		return 0;
	}
	void Dinic() {
		int t;
		while (GetLevel()) {
			for (int i = 1; i <= n; i++)PV[i] = G[i].size() - 1;
			while (t = BlockFlow(source, INF)) flow += t;
		}
	}
}G1;

vector<int>E[N_];

int Col[N_];

void DFS(int a, int pp, int col) {
	Col[a] = col;
	for (auto &x : E[a]) {
		if (x == pp)continue;
		DFS(x, a, 3 - col);
	}
}

int main() {
	freopen("input.txt", "r", stdin);
	int i, a, b;
	scanf("%d", &n);
	G1.init(n + 2, n + 1, n + 2);
	for (i = 1; i < n; i++) {
		scanf("%d%d", &a, &b);
		E[a].push_back(b);
		E[b].push_back(a);
	}
	DFS(1, 0, 1);
	for (i = 1; i <= n; i++) {
		for (auto &x : E[i]) {
			if (Col[i] == 1) G1.Add_Edge(i, x, 1);
		}
		if (Col[i] == 1)G1.Add_Edge(G1.source, i, n - 1 - E[i].size());
		else G1.Add_Edge(i, G1.sink, n - 1 - E[i].size());
	}
	G1.Dinic();
	printf("%d\n", G1.flow);
	for (i = 1; i <= n; i++) {
		if (Col[i] == 1) {
			for (auto &x : G1.G[i]) {
				Edge tp = G1.E[x];
				if (tp.e >= 1 && tp.e <= n && !tp.f) {
				}
			}
		}
	}

}*/

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