Submission #73773

#	Time	Username	Problem	Language	Result	Execution time	Memory
73773		TuGSGeReL	Mecho (IOI09_mecho)	C++14	100 / 100	456 ms	6708 KiB

mecho

#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pub push_back
#define pob pop_back
#define ss second
#define ff first
#define ext exit(0)
using namespace std;
int n,s,l,r,x,y,zu[801][801],bo[801][801],ax,ay,h[4]={0,0,-1,1},v[4]={-1,1,0,0};
char c[801][801];
queue<pair<pair<int,int>,int> >q,p;
void dfs(){
	memset(bo,0,sizeof bo);
	bo[q.front().ff.ff][q.front().ff.ss]=1;
	zu[q.front().ff.ff][q.front().ff.ss]=0;
	while(!q.empty()){
		int ii=q.front().ff.ff,jj=q.front().ff.ss,zz=q.front().ss;
		for(int k=0;k<4;k++){
			if(ii+h[k]<=n && ii+h[k]>0 && jj+v[k]<=n && jj+v[k]>0 && c[ii+h[k]][jj+v[k]]!='T' && c[ii+h[k]][jj+v[k]]!='D' && !bo[ii+h[k]][jj+v[k]] && zu[ii+h[k]][jj+v[k]]>zz+s){
				bo[ii+h[k]][jj+v[k]]=1;
				zu[ii+h[k]][jj+v[k]]=zz+s;
				q.push(mp(mp(ii+h[k],jj+v[k]),zz+s));
			}
		}
		q.pop();
	}
}
bool can(int k){
	q=p;
	if(k>=zu[x][y]) return 0;
	memset(bo,0,sizeof bo);
	q.push(mp(mp(x,y),k));
	bo[x][y]=1;
	while(!q.empty()){
		int xx=q.front().ff.ff,yy=q.front().ff.ss,kk=q.front().ss;
		for(int i=0;i<4;i++){
			if(bo[ax][ay]) return 1;
			if(xx+h[i]>0 && xx+h[i]<=n && yy+v[i]>0 && yy+v[i]<=n && c[xx+h[i]][yy+v[i]]!='T' && !bo[xx+h[i]][yy+v[i]] && zu[xx+h[i]][yy+v[i]]>kk+1){
				bo[xx+h[i]][yy+v[i]]=1;
				q.push(mp(mp(xx+h[i],yy+v[i]),kk+1));
			}
		}
		q.pop();
	}
	return 0;
}
int main (){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>s;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>c[i][j];
			if(c[i][j]=='M') x=i,y=j;
			if(c[i][j]=='D') ax=i,ay=j;
			zu[i][j]=1e9;
		}
	}
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(c[i][j]=='H')q.push(mp(mp(i,j),0));
	dfs();
	if(can(0)==0) {
		cout<<-1;
		ext;
	}
	l=0,r=1e9;
	while(l+1!=r){
		ll mid=(l+r)/2;
		if(can(mid)) l=mid;
		else r=mid;
	}
	cout<<l/s;
}

• Subtask 1: 100 / 100