Submission #103696

#	Time	Username	Problem	Language	Result	Execution time	Memory
103696		1234	Mecho (IOI09_mecho)	C++14	2 / 100	468 ms	66560 KiB

mecho

#include <bits/stdc++.h>
using namespace std ;
 
bool b[805][805] , bm[805][805];  
string s[805] ; 
int fuck , X1 , Y1 , X2 , Y2 , n , ss , a[805][805] , H[805][805];
queue <pair <int , int > > q , qm; 
 
void good(int x , int y , int sss) {
	H[x][y]=sss ;  
	b[x][y]= 1 ;
	if(y-1>=0 && b[x][y-1]==0) q.push(make_pair(x , y-1)) ;  
	if(y+1 < n && b[x][y+1]==0) q.push(make_pair(x , y+1)) ;  
	if(x-1>=0 && b[x-1][y]==0) q.push(make_pair(x-1 , y)) ;  
	if(x+1 < n && b[x+1][y]==0) q.push(make_pair(x+1 , y)) ;  
}
 
bool pro(int mid) {
	int ll=0 ; 
	while (qm.empty()==0) {
		int siz=qm.size(); 
		int cnt=0 ; 
		while (siz--) {
			cnt++ ; 
			int x=qm.front().first ;  	
			int y=qm.front().second ;  	
			qm.pop() ;
			if(x==X2 && y==Y2) {
				fuck = cnt ; 
				break ; 
			} 
			bm[x][y] = 1 ; 
			if(y-1>=0 && bm[x][y-1]==0 &&  H[x][y-1] < (cnt/ss)+mid) qm.push(make_pair(x , y-1)) ;  
			if(y+1 < n && bm[x][y+1]==0 &&  H[x][y+1] < (cnt/ss)+mid) qm.push(make_pair(x , y+1)) ;  
			if(x-1>=0 && bm[x-1][y]==0 &&  H[x-1][y] < (cnt/ss)+mid) qm.push(make_pair(x-1 , y)) ;  
			if(x+1 < n && bm[x+1][y]==0 &&  H[x+1][y] < (cnt/ss)+mid) qm.push(make_pair(x+1 , y)) ;
		}
		if(fuck%ss==0 && fuck!=-1) {
			if(cnt/ss+mid > H[X2][Y2]) return 1 ;
			else return 0 ;  	
		}
		if(fuck%ss!=0 && fuck!=-1) {
			if(fuck/ss+1+mid > H[X2][Y2]) return 1 ;
			else return 0 ;  				
		}
	}
}
 
int main(){
	fuck = -1 ; 
	cin >> n >> ss ; 
	for(int i=0 ; i<n ; i++){
		cin >> s[i] ; 			
		for(int j=0 ; j<n ; j++){
			if(s[i][j]=='T') {
				b[i][j]=1 ; 
				bm[i][j]=1 ; 
			}
			if(s[i][j]=='H') {
				q.push(make_pair(i , j)) ; 
				b[i][j]=1 ; 
				bm[i][j] = 1 ; 
			}
			if(s[i][j]=='D'){
				X2=i ; 
				Y2=j ; 
			}
			if(s[i][j]=='M'){
				X1=i ; 
				Y1=j ;
				qm.push(make_pair(X1 , Y1)) ; 
			}
		}
	}	
	int cnt = 0 ; 
	while (q.empty()==0) {
		int siz=q.size() ;
		while (siz--){
			int x=q.front().first ; 
			int y=q.front().second ;
			q.pop() ; 
			good (x , y , cnt) ;
		} 
		cnt++ ;  
	}
	
	int m1=0 , m2=H[X2][Y2] ;  
	while (m1 != m2) {
		int mid=(m1+m2+1)/2 ; 
		if(1 == pro(mid) ) {
			m1=mid ; 
		}	
		else {
			m2=mid-1 ; 
		}
	}
	cout << m2 << endl ; 
}

Compilation message (stderr)

mecho.cpp: In function 'bool pro(int)':
mecho.cpp:19:6: warning: unused variable 'll' [-Wunused-variable]
  int ll=0 ; 
      ^~
mecho.cpp:47:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 2 / 100