Submission #996446

#	Time	Username	Problem	Language	Result	Execution time	Memory
996446		ramalzaher	Mecho (IOI09_mecho)	C++14	100 / 100	374 ms	9564 KiB

mecho

#include<bits/stdc++.h> 
#include<unordered_map>
#include<unordered_set>
using namespace std ;
const int N = 801 ;
const int T = 1000 ; 
int n , s;
char a[N][N] ; 
int dis[N][N] , vis[N][N] ;	
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
bool valid(int x , int y ) {
return x >= 0 && x < n && y >= 0 && y < n &&
	       (a[x][y] == 'G' || a[x][y] == 'M');}  
void bfs(vector<int> startx , vector<int> starty ){
queue<pair<int,int>> q;	
for (int i = 0; i < startx.size() ; i++)
{
q.push({startx[i] , starty[i] });
vis[startx[i]][starty[i]] = 1 ; 
dis[startx[i]][starty[i]] = 0 ;
}
while(q.size()){
	pair<int,int> p  = q.front() ;
	int x = p.first; 
	int y = p.second ;
	q.pop() ;	
	for (int i = 0; i < 4; i++)
	{
		int newx = x+dx[i];
		int newy = y+dy[i];
		if(valid(newx , newy) && vis[newx][newy] == 0){
		q.push({newx , newy });	
		dis[newx][newy] = dis[x][y]+1;
		vis[newx][newy] = 1 ;
			}
		}	
	}
}
bool viss[N][N] ;int diss[N][N];
int homex ,  homey ; 
 
bool bfss(int startx ,int starty , int TT  ) {
viss[startx][starty] = 1 ; 
diss[startx][starty] = 0 ;
queue<pair<int,int>> q; 
q.push({startx , starty });	
if(dis[startx][starty] <= TT) { q.pop() ; }  
while(q.size()){
auto &[x,y] = q.front() ; 
q.pop();	
	for (int i = 0; i < 4; i++)
	{
		int newx = x+dx[i];
		int newy = y+dy[i];
		if(viss[newx][newy] ==0 && valid(newx, newy) && (dis[newx][newy]-TT) > (((diss[x][y]+1)/s) ) ) {
			q.push( { newx,  newy } ); 
			diss[newx][newy] = diss[x][y]+1 ; 
			viss[newx][newy]= 1;
			}
	}	
}
for (int i = 0; i < 4; i++)
{
	int nx = homex+dx[i]; int ny=homey+dy[i] ;
	if(valid(nx,ny)&& ( diss[nx][ny]/s ) < ( dis[nx][ny]-TT ) && viss[nx][ny] )return 1 ;
}
return 0 ;

} 
void cls(){
	for (int i = 0; i <= n; i++)
	{
	for (int j = 0; j <= n ; j++)
	{
	viss[i][j]=vis[i][j]=0;
	diss[i][j]=0 ; 
	dis[i][j]= 0  ; 
	}
	}
	}

main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 cin >> n >> s  ; int mx , my ; 
 vector<int> stx , sty ;
for (int i = 0; i < n; i++)
{
	for (int j = 0; j < n ; j++)
	{
		cin >> a[i][j] ;
		if(a[i][j]=='H'){
		stx.push_back(i);
		sty.push_back(j);
		}else if(a[i][j]=='M'){mx=i;my=j;}else if(a[i][j]=='D'){homex=i;homey=j;}
	}
}
int l =0 , r = n*n ; 
while(l <= r ) 
{
cls();
int mid = (l+r)/2 ; 
bfs(stx,sty);
if(bfss(mx,my,mid)) {
	l = mid + 1; 
	}else r = mid - 1; 
}
cout<<l-1<<endl; 
return 0 ; 
}
	

Compilation message (stderr)

mecho.cpp: In function 'void bfs(std::vector<int>, std::vector<int>)':
mecho.cpp:17:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 | for (int i = 0; i < startx.size() ; i++)
      |                 ~~^~~~~~~~~~~~~~~
mecho.cpp: In function 'bool bfss(int, int, int)':
mecho.cpp:50:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   50 | auto &[x,y] = q.front() ;
      |       ^
mecho.cpp: In function 'void cls()':
mecho.cpp:76:22: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   76 |  viss[i][j]=vis[i][j]=0;
      |             ~~~~~~~~~^~
mecho.cpp: At global scope:
mecho.cpp:83:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   83 | main(){
      | ^~~~
mecho.cpp: In function 'int main()':
mecho.cpp:104:8: warning: 'my' may be used uninitialized in this function [-Wmaybe-uninitialized]
  104 | if(bfss(mx,my,mid)) {
      |    ~~~~^~~~~~~~~~~
mecho.cpp:104:8: warning: 'mx' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 100 / 100