Submission #1306748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306748		liangjeremy	Mecho (IOI09_mecho)	C++20	41 / 100	187 ms	11468 KiB

mecho

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
//using namespace __gnu_pbds;
using db=double;
using ll=int64_t;
using sint=__int128;
using lb=long double;
mt19937 rng(random_device{}()); 

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n,s; cin>>n>>s; vector<vector<char>>a(n+1,vector<char>(n+1)); 
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){ cin>>a[i][j]; }
	}
	queue<pair<int,int>>q; vector<vector<int>>hd(n+1,vector<int>(n+1,1e18)); pair<int,int>st; pair<int,int>ed; 
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(a[i][j]=='H'){
				q.push({i,j}); hd[i][j]=0; 
			}
			if(a[i][j]=='M')st={i,j}; 
			if(a[i][j]=='D')ed={i,j}; 
		}
	}
	int di[]={0,0,1,-1}; int dj[]={1,-1,0,0}; 
	while(q.size()){
		int i=q.front().fi; int j=q.front().se; q.pop();
		for(int k=0; k<4; k++){
			int ni=i+di[k]; int nj=j+dj[k]; 
			if(ni<1 || ni>n || nj<1 || nj>n || a[ni][nj]=='T' || hd[ni][nj]!=1e18)continue; 
			hd[ni][nj]=hd[i][j]+1; q.push({ni,nj}); 
		} 
	}
	auto calc=[&](int num){
		return (int)(num/s); 
	};
	auto check=[&](int t){
		if(hd[st.fi][st.se]<=t)return false; 
		queue<pair<int,int>>q; vector<vector<int>>dist(n+1,vector<int>(n+1,-1)); q.push(st); dist[st.fi][st.se]=t; 
		while(q.size()){
			int i=q.front().fi; int j=q.front().se; q.pop();
			for(int k=0; k<4; k++){
				int ni=i+di[k]; int nj=j+dj[k]; 
				if(ni<1 || ni>n || nj<1 || nj>n || a[ni][nj]=='T' || dist[ni][nj]!=-1)continue; 
				int nd=dist[i][j]+1; int stp=t+calc(nd-t-1); 
				if(stp<hd[ni][nj]){
					dist[ni][nj]=nd; q.push({ni,nj}); 
				}
			}
		}
		return dist[ed.fi][ed.se]!=-1; 
	};
	int left=0; int right=800*800;
	if(!check(0)){
		cout<<-1<<'\n'; return 0; 
	}  
	while(left<right){
		int mid=(left+right+1)>>1; 
		if(check(mid))left=mid; else right=mid-1; 
	}
	cout<<left<<'\n'; 
}
/*
Overhead the albatross hangs motionless upon the air
And deep beneath the rolling waves in labyrinths of coral caves
The echo of a distant time comes willowing across the sand
And everything is green and submarine
 
And no one showed us to the land
And no one knows the wheres or whys
But something stirs and something tries
And starts to climb towards the light
*/

• Subtask 1: 41 / 100