Submission #799533

#	Time	Username	Problem	Language	Result	Execution time	Memory
799533		Baytoro	Mecho (IOI09_mecho)	C++17	100 / 100	197 ms	6276 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fr first
#define sc second
#define endl "\n"
#define ll long long
//#define int long long
void fopn(string name){
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
const ll INF=1e18,mod=1e9,N=1e7+5;
int n,s;
char a[805][805];
pair<int,int> cur,last;
int dist[805][805][2];
vector<int> dx={1,-1,0, 0},
			dy={0, 0,1,-1};
bool okh(int x, int y){
	return (x>0 && x<=n && y>0 && y<=n && (a[x][y]=='M' || a[x][y]=='G' || a[x][y]=='H'));
}
bool okm(int x, int y){
	return (x>0 && x<=n && y>0 && y<=n && (a[x][y]=='M' || a[x][y]=='G' || a[x][y]=='D'));
}
queue<pair<int,int>> dq;
bool check(int D){
	if(dist[cur.fr][cur.sc][0]<=D) return 0;
	while(!dq.empty()) dq.pop();
	dq.push({cur.fr,cur.sc});
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
			dist[i][j][1]=0;
	}
	dist[cur.fr][cur.sc][1]=1;
	while(!dq.empty()){
		pair<int,int> a=dq.front();
		dq.pop();
		for(int i=0;i<4;i++){
			int x=a.fr+dx[i],y=a.sc+dy[i];
			int d=dist[a.fr][a.sc][1]+1;
			if(okm(x,y) && !dist[x][y][1]){
				if((d-1)/s+1+D<=dist[x][y][0]){
					dq.push({x,y});
					dist[x][y][1]=d;
				}
				if(x==last.fr && y==last.sc && (d-1)/s+D-((d-1)%s==0)<=dist[x][y][0]) return 1;
			}
		}
	}
	return dist[last.fr][last.sc][1];
}
void solve(){
	queue<pair<int,int>> dq;
	cin>>n>>s;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
			if(a[i][j]=='H'){
				dq.push({i,j});
				dist[i][j][0]=1;
			}
			else if(a[i][j]=='M')
				cur={i,j};
			else if(a[i][j]=='D')
				last={i,j};
		}
	}
	while(!dq.empty()){
		pair<int,int> a=dq.front();
		dq.pop();
		for(int i=0;i<4;i++){
			int x=a.fr+dx[i],y=a.sc+dy[i];
			if(okh(x,y) && !dist[x][y][0]){
				dist[x][y][0]=dist[a.fr][a.sc][0]+1;
				dq.push({x,y});
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dist[i][j][0]-=(dist[i][j][0]>0);
		}
	}
	dist[last.fr][last.sc][0]=1e9;
	int l=-1,r=1e9;
	while(l<r){
		int md=(l)+(r-l+1)/2;
		if(check(md)) l=md;
		else r=md-1;
	}
	cout<<l<<endl;
}
main(){
	ios;
	int T=1;
	//cin>>T;
	for(int i=1;i<=T;i++){
		//cout<<"Case #"<<i<<": ";
		solve();
	}
}

Compilation message (stderr)

mecho.cpp:97:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   97 | main(){
      | ^~~~
mecho.cpp: In function 'void fopn(std::string)':
mecho.cpp:13:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:14:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100