Submission #1172892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172892		mertbbm	Mecho (IOI09_mecho)	C++20	32 / 100	144 ms	11912 KiB

mecho

#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

void solve(){
	int n,k;
	cin >> n >> k;
	string arr[n];
	vector<pii>hive;
	pii st;
	pii ed;
	for(int x=0;x<n;x++){
		cin >> arr[x];
		for(int y=0;y<n;y++){
			if(arr[x][y]=='M'){
				st={x,y};
			}
			else if(arr[x][y]=='H'){
				hive.push_back({x,y});
			}
			else if(arr[x][y]=='D'){
				ed={x,y};
			}
		}
	}
	
	pii dir[4]={
		{0,1},
		{0,-1},
		{1,0},
		{-1,0},
	};
	
	queue<pii>q;
	
	int dist2[n+5][n+5];
	memset(dist2,-1,sizeof(dist2));
	for(auto it:hive){
		dist2[it.first][it.second]=0;
		q.push(it);
	}
	
	while(!q.empty()){
		pii cur=q.front();
		q.pop();
		
		for(auto it:dir){
			int nx=cur.first+it.first;
			int ny=cur.second+it.second;
			if(nx<0||ny<0||nx>=n||ny>=n) continue;
			if(dist2[nx][ny]!=-1) continue;
			if(arr[nx][ny]=='T'||arr[nx][ny]=='D') continue;
			dist2[nx][ny]=dist2[cur.first][cur.second]+1;
			q.push({nx,ny});
		}
	}
	
	int l=1;
	int r=2*n+5;
	int best=-1;
	int mid;
	
	while(l<=r){
		mid=(l+r)/2;
		
		int dist[n+5][n+5];
		memset(dist,-1,sizeof(dist));		
		dist[st.first][st.second]=k*mid;
		if(dist2[st.first][st.second]>mid) q.push(st);
		
		while(!q.empty()){
			pii cur=q.front();
			q.pop();
			for(auto it:dir){
				int nx=cur.first+it.first;
				int ny=cur.second+it.second;
				if(nx<0||ny<0||nx>=n||ny>=n) continue;
				if(arr[nx][ny]=='T') continue;
				if(dist[nx][ny]!=-1) continue;
				int nd=dist[cur.first][cur.second]+1;
				if(dist2[nx][ny]==-1||dist2[nx][ny]*k>nd){
					dist[nx][ny]=nd;
					q.push({nx,ny});
				}
			}
		}
		
		if(dist[ed.first][ed.second]!=-1){
			best=mid;
			l=mid+1;
		}
		else r=mid-1;
	}
	
	cout << best << "\n";
}
																   
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

• Subtask 1: 32 / 100