Submission #882842

#	Time	Username	Problem	Language	Result	Execution time	Memory
882842		abhinavshukla408	Mecho (IOI09_mecho)	C++17	84 / 100	343 ms	31232 KiB

mecho

#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <cassert>
#include <math.h>
 
using namespace std;
 
#define endl "\n"
#define int int64_t 
#define pb push_back
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define FOR0(i,a) FOR(i,0,a)
#define FOR1(i,a) for (int i = (1); i <= (a); ++i)
#define TRAV(a,x) for (auto& a: x)

using pii = pair<int,int>;
using vi = vector<int>;
vi dx = {-1,0,1,0};
vi dy = {0,-1,0,1};
const int NMAX=801;
int N;
int S;
pii start={0,0};
pii end2={0,0};

bool f(int k,string grid[NMAX][NMAX],int distBees[NMAX][NMAX]){
	queue<pii> cur;
	cur.push(start);
	int dist[N][N];
	FOR0(i,N){
		FOR0(j,N){
			dist[i][j]=-1;
		}
	}
	dist[start.first][start.second]=0;
	while(!cur.empty()){
		pii curNode=cur.front();
		cur.pop();
		FOR0(i,4){
			int newR=curNode.first+dx[i];
			int newC=curNode.second+dy[i];
			if(newR<0 || newR>=N || newC<0 || newC>=N){continue;}
			if((grid[newR][newC]=="G" || grid[newR][newC]=="D") && dist[newR][newC]==(-1)){
				if((distBees[newR][newC]-k)>((dist[curNode.first][curNode.second]+1)/S)){
					//cout<<newR<<" "<<newC<<endl;
					dist[newR][newC]=dist[curNode.first][curNode.second]+1;
					cur.push({newR,newC});
				}
			}
		}
	}
	// FOR0(i,N){
	// 	FOR0(j,N){
	// 		cout<<dist[i][j]<<" ";
	// 	}
	// 	cout<<endl;
	// }
	bool ans=false;
	FOR0(i,4){
			int newR=end2.first+dx[i];
			int newC=end2.second+dy[i];
			if(newR<0 || newR>=N || newC<0 || newC>=N){continue;}
			if((grid[newR][newC]=="G" || grid[newR][newC]=="D") && dist[newR][newC]!=(-1)){
				
					//cout<<newR<<" "<<newC<<endl;
					ans=true;
				
			}
	}
	return ans;

}

int last_true(int lo, int hi,string grid[NMAX][NMAX],int distBees[NMAX][NMAX]) {
	// if none of the values in the range work, return lo - 1
	lo--;
	while (lo < hi) {
		// find the middle of the current range (rounding up)
		int mid = lo + (hi - lo + 1) / 2;
		if (f(mid,grid,distBees)) {
			// if mid works, then all numbers smaller than mid also work
			lo = mid;
		} else {
			// if mid does not work, greater values would not work either
			hi = mid - 1;
		}
	}
	return lo;
}


int32_t main(){

	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	// cout<<"yo"<<endl;
	// return 0;
	cin>>N>>S;
	string grid[NMAX][NMAX];
	int distBees[NMAX][NMAX];
	
	queue<pii> cur;
	FOR0(r,N){
		string in;
		cin>>in;
		FOR0(c,N){
			distBees[r][c]=-1;
			grid[r][c]=(in.at(c));
			if(grid[r][c]=="H"){
				cur.push({r,c});
				distBees[r][c]=0;
			}
			if(grid[r][c]=="M"){
				start={r,c};
			}
			if(grid[r][c]=="D"){
				end2={r,c};
			}
		}
	}
	// return 0;
	while(!cur.empty()){
		pii curNode=cur.front();
		int curR=curNode.first;
		int curC=curNode.second;
		cur.pop();
		FOR0(i,4){
				int newR=curNode.first+dx[i];
				int newC=curNode.second+dy[i];
				if(newR<0 || newR>=N || newC<0 || newC>=N){continue;}
				if(grid[newR][newC]!="T" && distBees[newR][newC]==(-1)){
					distBees[newR][newC]=distBees[curR][curC]+1;
					cur.push({newR,newC});
				}
		}
	}
	// FOR0(i,N){
	// 	FOR0(j,N){
	// 		cout<<distBees[i][j]<<" ";
	// 	}
	// 	cout<<endl;
	// }
	// cout<<endl;
	// cout<<f(1,grid,distBees)<<endl;
	// return 0;
	int ans=last_true(0,100000000,grid,distBees);
	if(ans==100000000){
		ans=-1;
	}
	cout<<ans<<endl;
	



	return 0;
}

• Subtask 1: 84 / 100