Submission #1241403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241403		sam230609	Mecho (IOI09_mecho)	C++20	100 / 100	144 ms	11592 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
char a[805][805]; ll dx[]={1,0,0,-1},dy[]={0,-1,1,0}; pair<ll,ll> start,d; queue<pair<ll,ll>> q; ll n,s,res=-1,t[805][805],dist[805][805];
bool kt( ll x, ll y, ll u, ll v){
	return ((x>0 && x<=n) && (y>0 && y<=n) && (t[x][y]>t[u][v]+1) && (a[x][y]!='T') && (a[x][y]!='D'));
}
bool choke( ll x, ll y, ll u, ll v, ll c){
	return ((x>0 && x<=n) && (y>0 && y<=n) && (dist[x][y]>dist[u][v]+1) && ((dist[u][v]+1)/s+c<t[x][y]) && (a[x][y]!='T'));
}
void fill(){
	while(!q.empty()){
		ll u=q.front().fi,v=q.front().se; q.pop();
		for(ll i=0;i<=3;i++){
			ll x=dx[i]+u,y=dy[i]+v; if(kt(x,y,u,v)) t[x][y]=t[u][v]+1,q.push({x,y});
		}
	}
}
bool check(ll c){
	for(ll i=1;i<=n;i++){
		for(ll j=1;j<=n;j++) dist[i][j]=1e9;
    }dist[start.fi][start.se]=0; q.push(start);
	while(!q.empty()){
		ll u=q.front().fi,v=q.front().se; q.pop();
		for(ll i=0;i<=3;i++){
			ll x=dx[i]+u,y=dy[i]+v; if(choke(x,y,u,v,c)) dist[x][y]=dist[u][v]+1,q.push({x,y});
		}
	}return dist[d.fi][d.se]!=1e9 && t[start.fi][start.se]>c;
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cin >>n>>s;
	for(ll i=1;i<=n;i++) for(ll j=1;j<=n;j++) t[i][j]=1e9;
	for(ll i=1;i<=n;i++) for(ll j=1;j<=n;j++){
        cin >>a[i][j]; if(a[i][j]=='H') t[i][j]=0,q.push({i,j}); if(a[i][j]=='M') start={i,j}; if(a[i][j]=='D') d={i,j};
    }fill(); ll l=0,r=805*805;
	while(l<=r){
		ll mid=(l+r)/2; if(check(mid)) l=mid+1,res=mid; else r=mid-1;
	}cout <<res;
}

• Subtask 1: 100 / 100