Submission #1092620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092620		4QT0R	Mecho (IOI09_mecho)	C++17	60 / 100	134 ms	7008 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>

char tab[802][802];
int xcor[4]={0,1,0,-1};
int ycor[4]={1,0,-1,0};

int dist[802][802];
int oo=1e9;
int n,s;

void prep(){
	queue<pii> q;
	for (int i = 1; i<=n; i++){
		for (int j = 1; j<=n; j++){
			dist[i][j]=oo;
			if (tab[i][j]=='H'){
				q.push({i,j});
				dist[i][j]=0;
			}
		}
	}
	while(q.size()){
		auto [x,y]=q.front();
		q.pop();
		for (int i = 0; i<4; i++){
			int u=x+xcor[i];
			int v=y+ycor[i];
			if (tab[u][v]=='G' && dist[u][v]>dist[x][y]+1){
				dist[u][v]=dist[x][y]+1;
				q.push({u,v});
			}
		}
	}
}

int vis[802][802];
int iter=0;
pii st,nd;

bool bfs(int waiting){
	queue<pair<pii,int>> q;
	if (dist[st.first][st.second]<=waiting)return false;
	q.push({st,0});
	while(q.size()){
		auto [pol,d]=q.front();
		if (pol==nd)return true;
		q.pop();
		for (int i = 0; i<4; i++){
			int u=pol.first+xcor[i];
			int v=pol.second+ycor[i];
			if ((tab[u][v]=='G'||tab[u][v]=='D') && vis[u][v]!=iter && (dist[u][v]>waiting+(d+1)/s)){
				vis[u][v]=iter;
				q.push({{u,v},d+1});
			}
		}
	}
	return false;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> s;
	for (int i = 1; i<=n; i++){
		for (int j = 1; j<=n; j++){
			cin >> tab[i][j];
			if (tab[i][j]=='M')st={i,j};
			if (tab[i][j]=='D')nd={i,j};
		}
	}
	prep();
	int l=-1,p=1e4,md;
	while(l<p){
		md=(l+p+1)/2;
		iter++;
		if (bfs(md))l=md;
		else p=md-1;
	}
	cout << l << '\n';
}

• Subtask 1: 60 / 100