Submission #1201828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201828		PlayVoltz	Mecho (IOI09_mecho)	C++20	11 / 100	478 ms	131072 KiB

mecho

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
using namespace std;

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int n, k, dy[4]={0, 0, -1, 1}, dx[4]={1, -1, 0, 0};
vector<string> graph;

bool can(int mid){
	queue<pii> bee, bear, nbee, nbear;
	vector<vector<bool> > visited(n, vector<bool>(n, 0));
	for (int i=0; i<n; ++i)for (int j=0; j<n; ++j)if (graph[i][j]=='H')visited[i][j]=1, bee.push(mp(i, j));
	while (mid--){
		while (bee.size()){
			int x=bee.front().fi, y=bee.front().se;
			bee.pop();
			for (int i=0; i<4; ++i){
				int nx=x+dx[i], ny=y+dy[i];
				if (nx<0||ny<0||nx>=n||ny>=n||graph[nx][ny]=='T'||graph[nx][ny]=='D'||visited[nx][ny])continue;
				visited[nx][ny]=1;
				nbee.push(mp(nx, ny));
			}
		}
		swap(bee, nbee);
	}
	for (int i=0; i<n; ++i)for (int j=0; j<n; ++j)if (graph[i][j]=='M'){
		if (visited[i][j])return 0;
		else bear.push(mp(i, j));
	}
	while (bear.size()){
		for (int ooga=0; ooga<k; ++ooga){
			while (bear.size()){
				int x=bear.front().fi, y=bear.front().se;
				if (graph[x][y]=='D')return 1;
				bear.pop();
				for (int i=0; i<4; ++i){
					int nx=x+dx[i], ny=y+dy[i];
					if (nx<0||ny<0||nx>=n||ny>=n||graph[nx][ny]=='T'||visited[nx][ny])continue;
					nbear.push(mp(nx, ny));
				}
			}
			swap(bear, nbear);
		}
		while (bee.size()){
			int x=bee.front().fi, y=bee.front().se;
			bee.pop();
			for (int i=0; i<4; ++i){
				int nx=x+dx[i], ny=y+dy[i];
				if (nx<0||ny<0||nx>=n||ny>=n||graph[nx][ny]=='T'||graph[nx][ny]=='D'||visited[nx][ny])continue;
				visited[nx][ny]=1;
				nbee.push(mp(nx, ny));
			}
		}
		swap(bee, nbee);
	}
	return 0;
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	graph.resize(n);
	for (int i=0; i<n; ++i)cin>>graph[i];
	int low=-1, high=n*n+1;
	while (low+1<high){
		int mid=(low+high)/2;
		if (can(mid))low=mid;
		else high=mid;
	}
	cout<<low;
}

• Subtask 1: 11 / 100