Submission #298407

#	Time	Username	Problem	Language	Result	Execution time	Memory
298407		bigg	Mecho (IOI09_mecho)	C++14	100 / 100	266 ms	8864 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 810;
const int INF = 1e9+7;
int dx[5] = {1,0,-1,0};
int dy[5] = {0,1,0,-1};
int inii, inij, desti, destj;
int n, s;
int distbees[MAXN][MAXN], distbear[MAXN][MAXN];
// 0 = grass
// 1 = bear
// 2 = bees
// 3 = trees
// 4 = dest
int grid[MAXN][MAXN];
bool bfsteste(int init){
	if(init >= distbees[inii][inij] || init >= distbees[desti][destj]) return 0;
	queue<pair<int, int > > q;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			distbear[i][j] = INF;
		}
	}
	distbear[inii][inij] = 0;
	q.push(make_pair(inii, inij));
	while(!q.empty()){
		int i = q.front().first;
		int j = q.front().second;
		q.pop();
		for(int v = 0; v < 4; v++){
			int ii = i + dx[v];
			int jj = j + dy[v];
			if(!ii || !jj || ii > n || jj > n || distbear[ii][jj] < INF || grid[ii][jj] == 3) continue;
			if(init + (distbear[i][j] + 1)/s <  distbees[ii][jj]){

				q.push(make_pair(ii,jj));
				distbear[ii][jj] = distbear[i][j] + 1;
			}
		}
	}
	//printf("%d\n", distbear[desti][destj] );
	if(distbear[desti][destj] < INF) return true;
	return false;
}

void bfsbees(){
	queue<pair<int, int> > q;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			distbees[i][j] = INF;
			if(grid[i][j] == 2){
				//printf("%d %d\n", i, j);
				q.push(make_pair(i,j));
				distbees[i][j] = 0;
			}
		}
	}
	while(!q.empty()){
		int i = q.front().first;
		int j = q.front().second;
		q.pop();
		//printf("%lu\n",q.size() );
		for(int v = 0; v < 4; v++){
			int ii = i + dx[v];
			int jj = j + dy[v];
			if(!ii || !jj || ii > n || jj > n || distbees[ii][jj] < INF || grid[ii][jj] == 3 || grid[ii][jj] == 4){
				continue;
			}
			q.push(make_pair(ii,jj));
			distbees[ii][jj] = distbees[i][j] + 1;
			
		}
	}
	//printf("%d\n", distbees[desti][destj] );
}


int main(){
	scanf("%d %d", &n, &s);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			// 0 = grass
			// 1 = bear
			// 2 = bees
			// 3 = trees
			// 4 = dest
			char c;
			scanf(" %c", &c);
			if(c == 'M'){
				grid[i][j] = 1;
				inii = i;
				inij = j;
			}
			if(c == 'H') grid[i][j] = 2;
			if(c == 'T') grid[i][j] = 3;
			if(c == 'D'){
				grid[i][j] = 4;
				desti = i;
				destj = j;
			}
		}
	}
	//printf("%d %d\n", desti, destj );
	bfsbees();
	int l = -1, r = n * n;
	while(l + 1 < r){
		int mid = (l+r)>>1;
		if(bfsteste(mid)) l = mid;//, printf("oi\n");
		else r = mid;
	}
	printf("%d\n",l );
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |  scanf("%d %d", &n, &s);
      |  ~~~~~^~~~~~~~~~~~~~~~~
mecho.cpp:88:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   88 |    scanf(" %c", &c);
      |    ~~~~~^~~~~~~~~~~

• Subtask 1: 100 / 100