Submission #1277830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277830		WH8	Mecho (IOI09_mecho)	C++20	56 / 100	138 ms	6156 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ld long double
int dir[4][2]={{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
signed main(){
	int n,s;cin>>n>>s;
	char mat[n][n];
	int sx,sy,ex,ey;
	queue<pair<int,int>> lol;
	vector<vector<int>> ft(n, vector<int>(n, 1e9));
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>mat[i][j];
			if(mat[i][j]=='M'){
				sx=i,sy=j;
			}
			else if(mat[i][j]=='H'){
				lol.push({i,j});
				ft[i][j]=0;
			}
			else if(mat[i][j]=='D'){
				ex=i,ey=j;
			}
		}
	}
	while(!lol.empty()){
		auto [x,y]=lol.front();lol.pop();
		for(int i=0;i<4;i++){
			int nx=x+dir[i][0], ny=y+dir[i][1];
			if(nx < 0 or nx >= n or ny <0 or ny>=n or mat[nx][ny]=='D' or mat[nx][ny]=='T' or
			ft[nx][ny] < 1e9)continue;
			ft[nx][ny]=ft[x][y]+1;
			lol.push({nx,ny});
		}
	}
	int l=-1, r=1601, m;
	if(sx==ex and sy==ey){
		cout<<ft[sx][sy]-1;
		return 0;
	}
	while(l<r-1){
		m=(l+r)/2;
		vector<vector<int>> dist(n, vector<int>(n, 1e9));
		dist[sx][sy]=0;
		queue<pair<int,int>> q;
		q.push({sx,sy});
		//~ printf("m is %lld\n", m);
		while(!q.empty()){
			
			auto [x,y]=q.front();q.pop();
			
			for(int i=0;i<4;i++){
				int nx=x+dir[i][0], ny=y+dir[i][1], nd=dist[x][y]+1;
				if(nx < 0 or nx >= n or ny <0 or ny>=n or
				mat[nx][ny]=='T' or m+nd/s >= ft[nx][ny] or dist[nx][ny] < 1e9)continue;
				//~ printf("going to %lld %lld, dist is nd %lld, m + nd/s is %lld, ft is %lld\n", x, y, nd, m+nd/s,ft[nx][ny]);
				dist[nx][ny]=nd;
				q.push({nx,ny});
			}
		}
		if(dist[ex][ey] < 1e9)l=m;
		else r=m;
	}
	cout<<l;
}
	

• Subtask 1: 56 / 100