Submission #59943

#	Time	Username	Problem	Language	Result	Execution time	Memory
59943		Tenuun	Mecho (IOI09_mecho)	C++17	50 / 100	1098 ms	6908 KiB

mecho

#include<bits/stdc++.h>

using namespace std;

int n, s, u, V, x, y, z;
int a[803][803], dx[4]={0, 0, 1, -1}, dy[4]={1, -1, 0, 0};
int bear[803][803];

vector<string> v;
vector<pair<int, int> >bee, o;
queue<pair<int, int>>q, b;

bool BFS(){
	queue<pair<pair<int, int>, int> >t;
	t.push({{x, y}, 0});
	bear[x][y]=0;
	while(!t.empty()){
		if(t.front().second>=s) return false;
		x=t.front().first.first, y=t.front().first.second, z=t.front().second;
		t.pop();
		if(a[x][y]!=-1) continue;
		for(int i=0; i<4; i++){
			if(v[x+dx[i]][y+dy[i]]=='D') return true;
			if(v[x+dx[i]][y+dy[i]]=='G' && a[x+dx[i]][y+dy[i]]==-1 && (bear[x+dx[i]][y+dy[i]]>bear[x][y]+1 || bear[x+dx[i]][y+dy[i]]==-1)){
				bear[x+dx[i]][y+dy[i]]=z+1;
				if(z+1>=s) o.push_back({x+dx[i], y+dy[i]});
				else t.push({{x+dx[i], y+dy[i]}, z+1});
			}
		}
	}
	return false;
}

bool check(int m){
	int curr;
	for(int i=0; i<bee.size(); i++){
		x=bee[i].first, y=bee[i].second;
		a[x][y]=0;
		q.push(bee[i]);
	}
	b.push({u, V});
	bear[u][V]=0;
	while(!q.empty()){
		x=q.front().first, y=q.front().second;
		curr=z=a[x][y];
		if(z>=m){
			while(!b.empty()){
				x=b.front().first, y=b.front().second;
				b.pop();
				if(BFS()) return true;
			}
			for(int i=0; i<o.size(); i++) b.push(o[i]);
			o.clear();
		}
		while(!q.empty() && a[q.front().first][q.front().second]==curr){
			x=q.front().first, y=q.front().second;
			q.pop();
			for(int i=0; i<4; i++){
				if((v[x+dx[i]][y+dy[i]]=='G' || v[x+dx[i]][y+dy[i]]=='M')&& a[x+dx[i]][y+dy[i]]==-1){
					a[x+dx[i]][y+dy[i]]=a[x][y]+1;
					q.push({x+dx[i], y+dy[i]});
				}
			}
		}	
	}
	return false;
}

void solve(){
	int l=0, r=(n+1)*n, m=(l+r+1)/2;
	while(l<r){
		memset(a, -1, sizeof a);
		memset(bear, -1, sizeof bear);
		while(!q.empty())q.pop();
		while(!b.empty())b.pop();
		o.clear();
		if(check(m)) l=m;
		else r=m-1;
		m=(l+r+1)/2;
	}
	/*for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			cout << bear[i][j] << " ";
		}
		cout << endl;
	}*/
	memset(a, -1, sizeof a);
	memset(bear, -1, sizeof bear);
	while(!q.empty())q.pop();
	while(!b.empty())b.pop();
	o.clear();
	if(check(l)==false) cout << -1;
	else cout << l;
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> s;
	string tmp, k;
	for(int i=0; i<n+2; i++) tmp+='T';
	v.push_back(tmp);
	for(int i=1; i<=n; i++){
		cin >> k;
		k='T'+k+'T';
		for(int j=1; j<=n; j++){
			if(k[j]=='M'){
				u=i, V=j;
			}
			if(k[j]=='H'){
				bee.push_back({i, j});
			}
		}
		v.push_back(k);
	}
	v.push_back(tmp);
	solve();
	return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'bool check(int)':
mecho.cpp:36:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<bee.size(); i++){
               ~^~~~~~~~~~~
mecho.cpp:52:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0; i<o.size(); i++) b.push(o[i]);
                 ~^~~~~~~~~

• Subtask 1: 50 / 100