Submission #103684

#	Time	Username	Problem	Language	Result	Execution time	Memory
103684		turbat	Mecho (IOI09_mecho)	C++14	42 / 100	805 ms	3976 KiB

mecho

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using pii = pair<int, int>;
using vi = vector <int>;
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define ll long long
#define ook order_of_key
#define fbo find_by_order
#define sq(x) (x) * (x)
#define N 805

int x, y, posx, posy, n, s;
int ax[4] = {0, 0, 1, -1};
int ay[4] = {1, -1, 0, 0}; 
string st[N];
queue <pii> que, q, bfs, mecho;
bool used[N][N], vis[N][N], pass[N][N];

bool check(int curx, int cury){
	if (curx < n && cury < n && curx >= 0 && cury >= 0 && !used[curx][cury]) return true;
	return false;
}

bool can(int time){;
	que = q;
	mecho.push(mp(x, y));
	memset(pass, 0, sizeof pass);
	pass[x][y] = 1;
	for (int i = 0;i < n;i++)
		for (int j = 0;j < n;j++)
			used[i][j] = vis[i][j];
	while (time--){
		bfs = que;
		while(!que.empty()) que.pop();
		while (!bfs.empty()){
			pii pos = bfs.front();
			bfs.pop();
			for (int i = 0;i < 4;i++)
				if (check(pos.F + ax[i], pos.S + ay[i]) && st[pos.F + ax[i]][pos.S + ay[i]] != 'T')
					que.push(mp(pos.F + ax[i], pos.S + ay[i])), used[pos.F + ax[i]][pos.S + ay[i]] = 1;
		} 
	}
	while (!used[posx][posy]){
		int tmp = s;
		while (tmp--){
			bfs = mecho;
			while (!mecho.empty()) mecho.pop();
			while (!bfs.empty()){
				pii pos = bfs.front();
				bfs.pop();
				if (pos.F == posx && pos.S == posy) return true;			
				if (!used[pos.F][pos.S])
					for (int i = 0;i < 4;i++)
						if (check(pos.F + ax[i], pos.S + ay[i]) && st[pos.F + ax[i]][pos.S + ay[i]] != 'T'
							&& !pass[pos.F + ax[i]][pos.S + ay[i]])
							mecho.push(mp(pos.F + ax[i], pos.S + ay[i])), pass[pos.F + ax[i]][pos.S + ay[i]] = 1;
			}
		}
		bfs = que;
		while (!que.empty()) que.pop();
		while (!bfs.empty()){
			pii pos = bfs.front();
			bfs.pop();
			for (int i = 0;i < 4;i++)
				if (check(pos.F + ax[i], pos.S + ay[i]) && st[pos.F + ax[i]][pos.S + ay[i]] != 'T')
					que.push(mp(pos.F + ax[i], pos.S + ay[i])), used[pos.F + ax[i]][pos.S + ay[i]] = 1;
		} 
	}
	return false;
}

int main (){
	cin >> n>> s;
	for (int i = 0;i < n;i++)
		cin >> st[i];
	for (int i = 0;i < n;i++)
		for (int j = 0;j < n;j++){
			if (st[i][j] == 'M') x = i, y = j;
			if (st[i][j] == 'D') posx = i, posy = j;
			if (st[i][j] == 'H') q.push(mp(i, j)), vis[i][j] = 1;
		}
	int l = 0, r = n * n;
	while (l != r){
		int mid = (l + r + 1) / 2;
		if (can(mid)) l = mid;
		else r = mid - 1;
	}
	if (can(l)) cout << l<< endl;
	else cout << -1 << endl;
}

• Subtask 1: 42 / 100