Submission #1221279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221279		ChuanChen	Mecho (IOI09_mecho)	C++20	26 / 100	356 ms	131072 KiB

mecho

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

const int MAXN = 808;

int n, s, fx, fy, mx, my;
char g[MAXN][MAXN];

#define ff first
#define ss second
unsigned short int dist[MAXN][MAXN], type[MAXN][MAXN];
//type: 0 -- grass, 1 -- mecho, 2 -- hive, 3 -- tree;

int dx[] = {0, 1, 0, -1},
	dy[] = {1, 0, -1, 0};
bool inbound(int x, int y){
	return 1<=x && x <= n && 1 <= y && y <= n;
}
void print(){
	for(int x = 1; x <= n; x++){
		for(int y = 1; y <= n; y++)
			cout << type[x][y];
		cout << '\n';
	}
	cout << '\n';
}
queue<pair<int, int>> bq, mq;

void expandBee(){
	if(bq.empty()) return;
	int x = bq.front().ff, y = bq.front().ss;
	int dini = dist[x][y];
	while(!bq.empty()){
		int x = bq.front().ff, y = bq.front().ss;
		if(dist[x][y] > dini) break;
		bq.pop();
		for(int i = 0; i < 4; i++){
			int nx = x+dx[i], ny = y+dy[i];
			if(!inbound(nx, ny)) continue;
			if(type[nx][ny] < 2){
				type[nx][ny] = 2;
				dist[nx][ny] = dist[x][y]+1;
				bq.push({nx, ny});
			}
		}
	}
}

void expandMecho(){
	// while(!mq.empty()){
	// 	int x = mq.front().ff, y = mq.front().ss;
	// 	if(type[x][y] == 2) mq.pop();
	// 	else break;
	// }
	if(mq.empty()) return;
	int x = mq.front().ff, y = mq.front().ss;
	int dini = dist[x][y];
	while(!mq.empty()){
		int x = mq.front().ff, y = mq.front().ss;
		if(dist[x][y] >= dini+s) break;
		mq.pop();
		if(type[x][y] != 1) continue;
		for(int i = 0; i < 4; i++){
			int nx = x+dx[i], ny = y+dy[i];
			if(!inbound(nx, ny)) continue;
			if(type[nx][ny] < 2 || type[nx][ny] == 4){
				type[nx][ny] = 1;
				dist[nx][ny] = dist[x][y]+1;
				mq.push({nx, ny});
			}
		}
	}
}

void clear(queue<pair<int, int>> &q){
	queue<pair<int, int>> empty;
	swap(q, empty);
}

bool guess(int m){
	clear(mq);
	clear(bq);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			dist[i][j] = 0;
			if(g[i][j] == 'G') type[i][j] = 0;
			else if(g[i][j] == 'M') type[i][j] = 1, mq.push({i, j});
			else if(g[i][j] == 'H') type[i][j] = 2, bq.push({i, j});
			else if(g[i][j] == 'T') type[i][j] = 3;
			else if(g[i][j] == 'D') type[i][j] = 4;
		}
	}
	for(int i = 1; i <= m; i++){
		expandBee();
		if(type[mx][my] == 2) return false;
	} 
	while(type[fx][fy] == 4){
		expandMecho();
		if(bq.empty()) return false;
		if(type[fx][fy] == 1) return true;
		expandBee();
	}
	return false;
}

int main(){
	cin >> n >> s;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++){
			cin >> g[i][j];
			if(g[i][j] == 'D') fx = i, fy = j;
			if(g[i][j] == 'M') mx = i, my = j;
		}
	if(!guess(0)){
		cout << -1;
		return 0;
	}
	int l = 0, r = 640000;
	while(l < r){
		int m = (l+r+1)/2;
		if(guess(m)) l = m;
		else r = m-1;
	}
	cout << l << '\n';
}

• Subtask 1: 26 / 100