Submission #947345

#	Time	Username	Problem	Language	Result	Execution time	Memory
947345		narsuk	Mecho (IOI09_mecho)	C++17	100 / 100	687 ms	9896 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
//
#define ll long long int
 
#define endl "\n"; 
 
const int maxn = 801;

// array<int,n>
// pq 


int n,st;

pair<int,int>mv[4]={ {0,1},{0,-1} , {1,0}, {-1,0} };

char g[maxn][maxn];
char g1[maxn][maxn];
char g2[maxn][maxn];

bool val(int x , int y){
	if(x<0 || x>=n || y<0 || y>=n || g[x][y]=='T' )return 0;
	return 1;
}
 

int xc,yc;
int xcc;
int ycc;
int beetime[maxn][maxn];

void bbfs(){
	int vis[n][n];
	queue<pair<pair<int,int>,int>>q;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			beetime[i][j]=INT_MAX;
			if(g1[i][j]=='H'){
				q.push({{i,j},0}); 
			}
			vis[i][j]=0;
		}
	}
	while(!q.empty()){
		pair<int,int>cur;
		cur=q.front().first;
		int dt = q.front().second;
		q.pop();
		if(vis[cur.first][cur.second])continue;
		vis[cur.first][cur.second]=1;

		if(g1[cur.first][cur.second]=='D' || g1[cur.first][cur.second]=='T'){
			continue;
		} 
		beetime[cur.first][cur.second]=dt;
		// cout<<cur.first<<" "<<cur.second<<endl;
		for(auto ele : mv){
			int xx = cur.first+ele.first;
			int yy = cur.second+ele.second;
			if(val(xx,yy)){
				q.push({{xx,yy},dt+1});
			}
		}
	}

}




// int mbfs(int x){
bool tme(int marc , int bee){
	int ccur = marc/st;
	// if(ccur*st!=marc){
	// 	return (marc/st)-1<bee;
	// }
	return marc/st <bee;
}

 

bool check(int x){

	bbfs();


	queue<pair<pair<int,int>,int>>q;
	bool vis[n][n];
	int dist[n][n];
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			vis[i][j]=0;
			dist[i][j]=INT_MAX;
		}
	}

	q.push({{xc,yc},0});
	if(beetime[xc][yc]<=x)q.pop();
	while(!q.empty()){
		pair<int,int>cur=q.front().first;
		int dt = q.front().second;
		dist[cur.first][cur.second]=dt;
		q.pop();
		if(vis[cur.first][cur.second])continue;
		vis[cur.first][cur.second]=1;
		if(g[cur.first][cur.second]=='D'){
			return 1;
		}

		for(auto ele :mv){
			int xx = cur.first+ele.first;
			int yy = cur.second+ele.second;

			if(val(xx,yy) && !vis[xx][yy] && tme(dt+1 , beetime[xx][yy]-x) && g[xx][yy]!='H'){
				q.push({{xx,yy} , dt+1});
			}
		}

	}
	// for(int i=0;i<n;i++){
	// 	for(int j=0;j<n;j++){
	// 		cout<<vis[i][j]<<" ";
	// 	}
	// 	cout<<endl;
	// }

	for(auto ele : mv){
		int xx = xcc+ele.first;
		int yy = ycc+ele.second;

		if(val(xx,yy) && vis[xx][yy]==1 && tme(dist[xx][yy] ,beetime[xx][yy]-x)){
		// cout<<xx<<" "<<yy<<endl;
			return 1;
		}
	}

	return 0;
}

void solu(){
	cin>>n>>st;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>g[i][j];
			g1[i][j]=g[i][j];
			if(g[i][j]=='M'){
				xc=i;
				yc=j;
			}
			if(g[i][j]=='D'){
				xcc = i;
				ycc = j;
			}
		}
	}
	// cout<<endl;
	int l=0;
	int r = n*n;
	int ans=0;
	while(l<r){
		int mid = l + (r-l+1)/2;
		// cout<<mid<<endl;
		if(check(mid)){
			ans=max(mid,ans);
			l=mid;
		}else{
			r=mid-1;
		}
	}
	if(!check(0)){
		cout<<"-1"<<endl;
		return;
	}
	// cout<<check(2)<<endl;
	// if(ans==0){
	// 	cout<<"-1"<<endl;
	// 	return;
	// }
	cout<<ans<<endl;


}
int main(){
		// ios_base::sync_with_stdio(0);
		// cin.tie(0);
		// int cass;
		// cin>>cass; 
		// for(int i=0;i<cass;i++)
		solu();
    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'bool tme(int, int)':
mecho.cpp:74:6: warning: unused variable 'ccur' [-Wunused-variable]
   74 |  int ccur = marc/st;
      |      ^~~~

• Subtask 1: 100 / 100