Submission #392502

#	Time	Username	Problem	Language	Result	Execution time	Memory
392502		Berted	Mecho (IOI09_mecho)	C++14	100 / 100	190 ms	7008 KiB

mecho

#include <iostream>
#include <queue>
#define pii pair<int, int>
#define fst first
#define snd second
using namespace std;

const int INF = 1e9;

int T, N, S;
string M[801];
int block[801][801], dist[801][801];

inline void preBFS()
{
	queue<pii> q;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++) block[i][j] = INF;
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (M[i][j] == 'H') 
			{
				block[i][j] = 0;
				q.push({i, j});
			}
			if (M[i][j] == 'T') {block[i][j] = 0;}
			if (M[i][j] == 'D') {block[i][j] = INF + 1;}
		}
	}
	while (q.size())
	{
		pii u = q.front(); q.pop();
		if (u.fst && block[u.fst - 1][u.snd] == INF)
		{
			block[u.fst - 1][u.snd] = block[u.fst][u.snd] + 1;
			q.push({u.fst - 1, u.snd});
		}
		if (u.fst + 1 < N && block[u.fst + 1][u.snd] == INF)
		{
			block[u.fst + 1][u.snd] = block[u.fst][u.snd] + 1;
			q.push({u.fst + 1, u.snd});
		}
		if (u.snd && block[u.fst][u.snd - 1] == INF)
		{
			block[u.fst][u.snd - 1] = block[u.fst][u.snd] + 1;
			q.push({u.fst, u.snd - 1});
		}
		if (u.snd + 1 < N && block[u.fst][u.snd + 1] == INF)
		{
			block[u.fst][u.snd + 1] = block[u.fst][u.snd] + 1;
			q.push({u.fst, u.snd + 1});
		}
	}
}

inline bool BFS(pii s, int x)
{
	queue<pii> q;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++) dist[i][j] = INF;
	}
	dist[s.fst][s.snd] = x * S;
	q.push({s.fst, s.snd});
	while (q.size())
	{
		pii u = q.front(); q.pop();
		if (M[u.fst][u.snd] == 'D') return 1;
		if (u.fst && block[u.fst - 1][u.snd] > (dist[u.fst][u.snd] + 1) / S && dist[u.fst - 1][u.snd] == INF)
		{
			dist[u.fst - 1][u.snd] = dist[u.fst][u.snd] + 1;
			q.push({u.fst - 1, u.snd});
		}
		if (u.fst + 1 < N && block[u.fst + 1][u.snd] > (dist[u.fst][u.snd] + 1) / S && dist[u.fst + 1][u.snd] == INF)
		{
			dist[u.fst + 1][u.snd] = dist[u.fst][u.snd] + 1;
			q.push({u.fst + 1, u.snd});
		}
		if (u.snd && block[u.fst][u.snd - 1] > (dist[u.fst][u.snd] + 1) / S && dist[u.fst][u.snd - 1] == INF)
		{
			dist[u.fst][u.snd - 1] = dist[u.fst][u.snd] + 1;
			q.push({u.fst, u.snd - 1});
		}
		if (u.snd + 1 < N && block[u.fst][u.snd + 1] > (dist[u.fst][u.snd] + 1) / S && dist[u.fst][u.snd + 1] == INF)
		{
			dist[u.fst][u.snd + 1] = dist[u.fst][u.snd] + 1;
			q.push({u.fst, u.snd + 1});
		}
	}
	return 0;
} 

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
  	cin >> N >> S;
  	for (int i = 0; i < N; i++) cin >> M[i];
  	preBFS();
  	int si, sj;
  	for (int i = 0; i < N; i++)
  	{
    	for (int j = 0; j < N; j++)
    	{
      	if (M[i][j] == 'M') {si = i; sj = j; break;}
    	}
  	}
 	int L = 0, R = block[si][sj];
  	while (L < R)
  	{
    	int M = L + R >> 1;
    	if (BFS({si, sj}, M)) {L = M + 1;}
    	else {R = M;}
  	}
  	cout << L - 1 << "\n";
	return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:114:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |      int M = L + R >> 1;
      |              ~~^~~
mecho.cpp:111:14: warning: 'sj' may be used uninitialized in this function [-Wmaybe-uninitialized]
  111 |   int L = 0, R = block[si][sj];
      |              ^
mecho.cpp:111:14: warning: 'si' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 100 / 100