Submission #683266

#	Time	Username	Problem	Language	Result	Execution time	Memory
683266		ajstillpracticin	Mecho (IOI09_mecho)	C++17	100 / 100	534 ms	7692 KiB

mecho

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define fi first
#define se second

int dx[4]{1,0,-1,0};
int dy[4]{0,1,0,-1};
char direc[4]{'R','U','L','D'};

void setIO(string filename=""){
	ios_base::sync_with_stdio(0); cin.tie(0);
	if(filename.size()){
		freopen((filename + ".in").c_str(), "r", stdin);
		freopen((filename + ".out").c_str(), "w", stdout);
	}
}

const int INF=(int) 1e9;
const int M= 1e9+7;
const ll MAXD = 1e18;

//
const int MAXN = 1e4;

int main() {

	setIO();
	
	int n,s;
	cin >> n >> s;

	string grid[n];
	for(int i=0;i<n;++i)
		cin >> grid[i];
	
	vector<pair<int,int>> hive;
	int mechox,mechoy,homex,homey;
	for(int i=0;i<n;++i)
		for(int j=0;j<n;++j){
			if(grid[i][j]=='M'){
				mechox=i;
				mechoy=j;
			} else if(grid[i][j]=='H'){
				hive.push_back({i,j});
			} else if(grid[i][j]=='D'){
				homex=i;
				homey=j;
			}
		}

	int l=0;
	int r=n*n;
	while(l<=r){
		bool bee_vis[n][n]{};
		bool me_vis[n][n]{};

		int bee_time[n][n];
		int me_time[n][n];

		memset(bee_time, 0 , sizeof(bee_time));
		memset(me_time, 0 , sizeof(me_time));

		int time=(l+r)/2;

		queue<pair<int,int>> q;

		for(auto i : hive){
			q.push({i.fi,i.se});
			bee_vis[i.fi][i.se]=1;
		}

		while(!q.empty()){
			int x=q.front().fi;
			int y=q.front().se;

			q.pop();

			for(int i=0;i<4;++i){
				int nx=x+dx[i],ny=y+dy[i];
				if(nx<0 || nx>=n || ny<0 || ny>=n)
					continue;
				if(!(grid[nx][ny]=='G' || grid[nx][ny]=='M') || bee_vis[nx][ny])
					continue;
				bee_time[nx][ny]=bee_time[x][y]+1;
				q.push({nx,ny});
				bee_vis[nx][ny]=1;
			}
		}

		q.push({mechox,mechoy});
		me_vis[mechox][mechoy]=1;
		if(bee_time[mechox][mechoy]<=time)
			q.pop();

		while(!q.empty()){
			int x=q.front().fi;
			int y=q.front().se;
			q.pop();

			for(int i=0;i<4;++i){
				int nx=x+dx[i],ny=y+dy[i];
				if(nx<0 || nx>=n || ny<0 || ny>=n)
					continue;
				if(!(grid[nx][ny]=='G' || grid[nx][ny]=='M') || me_vis[nx][ny])
					continue;
				if((me_time[x][y]+1)/s < bee_time[nx][ny]-time){
					me_vis[nx][ny]=1;
					q.push({nx,ny});
					me_time[nx][ny]=me_time[x][y]+1;
				}
			}
		}

		bool ans=0;
		for(int i=0;i<4;++i){
			int nx=homex+dx[i],ny=homey+dy[i];
			if(nx<0 || nx>=n || ny<0 || ny>=n)
				continue;
			if((me_time[nx][ny]/s)<bee_time[nx][ny]-time && me_vis[nx][ny]){
				ans=1;
				break;
			}
		}

		if(ans)
			l=time+1;
		else
			r=time-1;
	}

	cout << l-1 << "\n";
}

Compilation message (stderr)

mecho.cpp: In function 'void setIO(std::string)':
mecho.cpp:15:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   freopen((filename + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:16:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |   freopen((filename + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp: In function 'int main()':
mecho.cpp:94:29: warning: 'mechoy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   94 |   if(bee_time[mechox][mechoy]<=time)
      |      ~~~~~~~~~~~~~~~~~~~~~~~^
mecho.cpp:94:29: warning: 'mechox' may be used uninitialized in this function [-Wmaybe-uninitialized]
mecho.cpp:118:8: warning: 'homex' may be used uninitialized in this function [-Wmaybe-uninitialized]
  118 |    int nx=homex+dx[i],ny=homey+dy[i];
      |        ^~
mecho.cpp:118:23: warning: 'homey' may be used uninitialized in this function [-Wmaybe-uninitialized]
  118 |    int nx=homex+dx[i],ny=homey+dy[i];
      |                       ^~

• Subtask 1: 100 / 100