Submission #948092

#	Time	Username	Problem	Language	Result	Execution time	Memory
948092		packmani	Mecho (IOI09_mecho)	C++14	64 / 100	120 ms	7276 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
#define int long long int
int n,speed;
char inp[805][805];
int board[805][805];
bool visited[805][805];
queue<pair<int,int>> q;
pair<int,int> s,e;
int cr,cc,er,ec;
int dr[]={0,-1,0,1};
int dc[]={1,0,-1,0};
int maxTime=0;
int l,m,r;
int layer,tillNext,inNext;
void printBoard()
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			cout << board[i][j] << ' ';
		}
		cout << '\n';
	}
	cout << '\n';
}
bool bfs(int start)
{
	queue<pair<int,int>> tempq;
	memset(visited,0,sizeof(visited));
	int time=start;
	tempq.push({s.first,s.second});
	tillNext=1;
	inNext=0;
	layer=0;
	while(!tempq.empty())
	{
		cr = tempq.front().first;
		cc = tempq.front().second;
		tempq.pop();
		if(board[cr][cc]>time or inp[cr][cc]=='M')//bees have not reached this spot yet
		{
			//cout << time;
			for(int i=0;i<4;i++)
			{
				er = cr + dr[i];
				ec = cc + dc[i];
				if(er<0 or ec<0 or er>=n or ec>=n) continue;
				if(inp[er][ec]=='D') return 1;
				if(visited[er][ec]) continue;
				if(board[er][ec]==-1) continue;
				if(board[er][ec]<=time) continue;
				tempq.push({er,ec});
				visited[er][ec]=1;
				inNext++;
			}
		}
		tillNext--;
		if(tillNext==0)
		{
			tillNext = inNext;
			inNext = 0;
			layer++;
			if(layer%speed==0) time++;
		}
	}
	return 0;
}
int32_t main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	cin >> n >> speed;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			cin >> inp[i][j];
			if(inp[i][j]=='T') board[i][j]=0; //no one can traverse
			if(inp[i][j]=='H') 
			{
				board[i][j]=0; //not walkable since the 0th sec
				q.push({i,j});
			}
			if(inp[i][j]=='M') s={i,j};
			if(inp[i][j]=='D') e={i,j};
			if(inp[i][j]=='G') board[i][j] = 100000;
		}
	}
	//bees
	while(!q.empty())
	{
		cr = q.front().first;
		cc = q.front().second;
		q.pop();
		for(int i=0;i<4;i++)
		{
			er = cr + dr[i];
			ec = cc + dc[i];
			if(er<0 or ec<0 or er>=n or ec>=n) continue;
			if(board[er][ec]==-1 or board[er][ec]=='D') continue;
			if(board[er][ec]<=board[cr][cc]+1) continue;
			board[er][ec]=board[cr][cc]+1;
			q.push({er,ec});
			maxTime=max(maxTime,board[er][ec]);
		}
	}
	//printBoard();
	//cout << maxTime;
	//b-search answer in range(0,maxTime)
	/*for(int i=0;i<=maxTime;i++)
		cout << i << ' ';
	cout << '\n';
	for(int i=0;i<=maxTime;i++)
		cout << bfs(i) << ' ';
	cout << '\n';*/
	l=0;
	r=10000000;
	m = l + (r-l)/2;
	while(l<=r)
	{
		//cout << l << ' ' << r << ' ' << m << '\n';
		if(bfs(m)==1) l=m+1;
		else r=m-1;
		m = l + (r+0.5-l)/2;

	}
	if(m==0 and bfs(0)==0) cout << -1;
	else cout << m;
}

• Subtask 1: 64 / 100