Submission #53583

#	Time	Username	Problem	Language	Result	Execution time	Memory
53583		ho94949	Mecho (IOI09_mecho)	C++17	100 / 100	310 ms	6744 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int N, S;
char arr[1024][1024];
int dist[1024][1024];
bool vis[1024][1024];
bool valid(int x, int y)
{
	return 0<=x&&x<N&&0<=y&&y<N;
}
bool can(int t)
{
	queue<tuple<int, int, int> > Q;
	memset(vis, false, sizeof(vis));
	for(int i=0; i<N; ++i)
		for(int j=0; j<N; ++j)
			if(arr[i][j] == 'M')
			{
				if(dist[i][j] <= t*S) return false;
				Q.emplace(t*S, i, j);
			}
	while(!Q.empty())
	{
		int di, x, y; tie(di, x, y) = Q.front(); Q.pop();
		if(arr[x][y] == 'D') return true;
		for(int d=0; d<4; ++d)
		{
			int nx = x+"1210"[d]-'1';
			int ny = y+"0121"[d]-'1';
			if(!valid(nx, ny)) continue;
			if(arr[nx][ny] != 'G' && arr[nx][ny] != 'D') continue;
			if(dist[nx][ny] <= di+1) continue;
			if(vis[nx][ny]) continue;
			Q.emplace(di+1, nx, ny);
			vis[nx][ny] = true;
		}
	}
	return false;
}
void init()
{
	memset(dist, 0x3f, sizeof dist);
	queue<pair<int, int> > Q;
	for(int i=0; i<N; ++i)
		for(int j=0; j<N; ++j)
		{
			if(arr[i][j] == 'H')
			{
				Q.emplace(i, j);
				dist[i][j] = 0;
			}
		}
	while(!Q.empty())
	{
		int x, y; tie(x, y) = Q.front(); Q.pop();
		for(int d=0;d<4;++d)
		{
			int nx = x+"1210"[d] - '1';
			int ny = y+"0121"[d] - '1';
			if(!valid(nx, ny)) continue;
			if(arr[nx][ny] != 'G' && arr[nx][ny] != 'M') continue;
			if(dist[nx][ny] != INF) continue;
			dist[nx][ny] = dist[x][y]+S;
			Q.emplace(nx, ny);
		}
	}
}
int main()
{
	scanf("%d%d", &N, &S);
	for(int i=0; i<N; ++i)
		scanf("%s", arr[i]);
	int lo = -1; //pos
	int hi = N*N; //impos
	init();
	while(lo+1!=hi)
	{
		int mi = (lo+hi)/2;
		if(can(mi)) lo = mi;
		else hi = mi;
	}
	printf("%d\n", lo);
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &S);
  ~~~~~^~~~~~~~~~~~~~~~
mecho.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", arr[i]);
   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 100 / 100