Submission #60054

#	Time	Username	Problem	Language	Result	Execution time	Memory
60054		nvmdava	Mecho (IOI09_mecho)	C++17	100 / 100	536 ms	6528 KiB

mecho

#include <bits/stdc++.h>
#define mp make_pair
#define ff first
#define ss second
using namespace std;
int n,s;
int t[802][802];
char c[802][802];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int  chk[802][802];
queue<pair<int, int > > q;

bool pos(int x,int y, int now){
	memset(chk,0,sizeof(chk));
	if(now >= t[x][y]){
		return 0;
	}
	chk[x][y] = now;
	q.push(mp(x,y));
	while(!q.empty()){
		x = q.front().ff;
		y = q.front().ss;
		q.pop();
		for(int i = 0; i < 4; i++){
			if(c[x + dx[i]][y + dy[i]]=='D'){
				while(!q.empty()){
					q.pop();
				}
				return 1;
			}
			if(chk[x + dx[i]][y + dy[i]]==0 && t[x + dx[i]][y + dy[i]] > chk[x][y] + 1){
				chk[x + dx[i]][y + dy[i]] = chk[x][y] + 1;
				q.push( mp(x + dx[i] , y + dy[i]) );
			}
		}
	}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int i,j,xx,yy;
	cin>>n>>s;
	for(i = 1; i <= n; i++){
		for(j = 1; j <= n; j++){
			cin>>c[i][j];
			if(c[i][j]=='H'){
				q.push(mp(i,j));
			} else if(c[i][j]=='M'){
				xx=i;
				yy=j;
			}
		}
	}
	int x,y;
	while(!q.empty()){
		x=q.front().ff;
		y=q.front().ss;
		q.pop();
		for(i=0;i<4;i++){
			if((c[x + dx[i]][y + dy[i]]=='G'||c[x + dx[i]][y + dy[i]]=='M')&&t[x + dx[i]][y + dy[i]]==0){
				t[x + dx[i]][y + dy[i]] = t[x][y]+s;
				q.push(mp(x + dx[i] , y + dy[i]));
			}
		}
	}
	int l = 0 , r = 1e9,m;
	if(pos(xx,yy,0)==0){
		cout<<-1;
		return 0;
	}
	while(l + 1 != r){
		m = (l + r) / 2;
		if(pos(xx,yy,m)){
			l = m;
		} else {
			r = m;
		}
	}
	cout<<l/s;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:71:8: warning: 'yy' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if(pos(xx,yy,0)==0){
     ~~~^~~~~~~~~
mecho.cpp:71:8: warning: 'xx' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 100 / 100