Submission #281908

#	Time	Username	Problem	Language	Result	Execution time	Memory
281908		Plurm	Mecho (IOI09_mecho)	C++11	30 / 100	445 ms	6400 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
char t[1024][1024];
char test[1024][1024];
int dist[1024][1024];
int n, s;
class state{
public:
	int x,y,cw;
	state(int a, int b, int c): x(a), y(b), cw(c) {}
};
void propagateBees(queue<state>& q, int limit){
	while(!q.empty() && q.front().cw < limit){
		state cur = q.front();
		q.pop();
		int x = cur.x;
		int y = cur.y;
		int w = cur.cw+1;
		if(x > 1 && (test[x-1][y] == 'G' || test[x-1][y] == 'M') && dist[x-1][y] > w){
			dist[x-1][y] = w;
			test[x-1][y] = 'H';
			q.emplace(x-1, y, w);
		}
		if(x < n && (test[x+1][y] == 'G' || test[x+1][y] == 'M') && dist[x+1][y] > w){
			dist[x+1][y] = w;
			test[x+1][y] = 'H';
			q.emplace(x+1, y, w);
		}
		if(y > 1 && (test[x][y-1] == 'G' || test[x][y-1] == 'M') && dist[x][y-1] > w){
			dist[x][y-1] = w;
			test[x][y-1] = 'H';
			q.emplace(x, y-1, w);
		}
		if(y < n && (test[x][y+1] == 'G' || test[x][y+1] == 'M') && dist[x][y+1] > w){
			dist[x][y+1] = w;
			test[x][y+1] = 'H';
			q.emplace(x, y+1, w);
		}
	}
}
void propagateMecho(queue<state>& q, int limit){
	while(!q.empty() && q.front().cw <= limit){
		state cur = q.front();
		q.pop();
		int x = cur.x;
		int y = cur.y;
		if(test[x][y] != 'M') continue;
		int w = cur.cw+1;
		if(x > 1 && (test[x-1][y] == 'G' || test[x-1][y] == 'D') && dist[x-1][y] > w){
			dist[x-1][y] = w;
			test[x-1][y] = 'M';
			q.emplace(x-1, y, w);
		}
		if(x < n && (test[x+1][y] == 'G' || test[x+1][y] == 'D') && dist[x+1][y] > w){
			dist[x+1][y] = w;
			test[x+1][y] = 'M';
			q.emplace(x+1, y, w);
		}
		if(y > 1 && (test[x][y-1] == 'G' || test[x][y-1] == 'D') && dist[x][y-1] > w){
			dist[x][y-1] = w;
			test[x][y-1] = 'M';
			q.emplace(x, y-1, w);
		}
		if(y < n && (test[x][y+1] == 'G' || test[x][y+1] == 'D') && dist[x][y+1] > w){
			dist[x][y+1] = w;
			test[x][y+1] = 'M';
			q.emplace(x, y+1, w);
		}
	}
}
bool escapePossible(int days){
	queue<state> q, mq;
	int dx, dy;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			test[i][j] = t[i][j];
			dist[i][j] = 1e9;
			if(t[i][j] == 'H'){
				q.emplace(i,j,0);
				dist[i][j] = 0;
			}else if(t[i][j] == 'D'){
				dx = i;
				dy = j;
			}else if(t[i][j] == 'M'){
				mq.emplace(i,j,0);
				dist[i][j] = 0;
			}
		}
	}
	propagateBees(q, days);
	int lm = 0;
	int oldDays = days;
	while(!mq.empty() && !q.empty() && test[dx][dy] != 'M'){
		lm += s;
		propagateMecho(mq, lm);
		days++;
		propagateBees(q, days);
	}
	return test[dx][dy] == 'M';
}
int main(){
	scanf("%d%d",&n,&s);
	for(int i = 1; i <= n; i++){
		scanf("%s", t[i]+1);
	}
	int lo = 0;
	int hi = n*n;
	int mid;
	while(lo < hi){
		mid = (lo+hi+1)/2;
		if(escapePossible(mid)){
			lo = mid;
		}else{
			hi = mid-1;
		}
	}
	printf("%d\n", lo);
	return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'bool escapePossible(int)':
mecho.cpp:92:6: warning: unused variable 'oldDays' [-Wunused-variable]
   92 |  int oldDays = days;
      |      ^~~~~~~
mecho.cpp: In function 'int main()':
mecho.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  102 |  scanf("%d%d",&n,&s);
      |  ~~~~~^~~~~~~~~~~~~~
mecho.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  104 |   scanf("%s", t[i]+1);
      |   ~~~~~^~~~~~~~~~~~~~
mecho.cpp: In function 'bool escapePossible(int)':
mecho.cpp:73:10: warning: 'dy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |  int dx, dy;
      |          ^~
mecho.cpp:73:6: warning: 'dx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |  int dx, dy;
      |      ^~

• Subtask 1: 30 / 100