Submission #703216

#	Time	Username	Problem	Language	Result	Execution time	Memory
703216		AverageAmogusEnjoyer	Mecho (IOI09_mecho)	C++17	25 / 100	1091 ms	10672 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define nl '\n'
using ll = long long;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int N, S; cin >> N >> S;
	vector<vector<int>> grid(N, vector<int> (N));
	char c;
	pair<int, int> Mecho, Home;
	vector<pair<int, int>> hives;
	for (int a=0; a<N; a++) {
		for (int b=0; b<N; b++) {
			cin >> c;
			if (c == 'T') grid[a][b] = 0;
			if (c == 'G') grid[a][b] = 1;
			if (c == 'M') {
				grid[a][b] = 1;
				Mecho = {a, b};
			} 
			if (c == 'D') {
				grid[a][b] = 2;
				Home = {a, b};
			} 
			if (c == 'H') {
				grid[a][b] = 1;
				hives.pb({a, b});
			}
		}
	}
	ll a=0, b = 1e8;
	while (a <= b) {
		ll minutes = (a+b)/2;
		vector<vector<bool>> used(N, vector<bool> (N));
		vector<vector<bool>> UsedMecho(N, vector<bool> (N));
		deque<pair<bool, queue<pair<int, int>>>> q;
		//0 = bees
		//1 = Mecho
		for (auto hive: hives) {
			queue<pair<int, int>> myQ;
			myQ.push({hive.first, hive.second});
			q.push_front({0, myQ});
			used[hive.first][hive.second] = 1;
			UsedMecho[hive.first][hive.second] = 1;			
		}
		bool MechoIn = 0;
		vector<pair<int, int>> moves = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
		//destra, sinistra, sotto, sopra
		vector<vector<int>> dist(N, vector<int> (N)), distBee(N, vector<int> (N));
		while(q.size() != 0) {
			auto t = q.front(); q.pop_front();
			bool isMecho; queue<pair<int, int>> myQ; tie(isMecho, myQ) = t;
			queue<pair<int, int>> last;
			if (isMecho) {
				if (myQ.size() == 0) break;
				queue<pair<int, int>> Mechos;
				while(!myQ.empty()) {
					int x = myQ.front().first, y = myQ.front().second; myQ.pop();
					Mechos.push({x, y});
					dist[x][y] = 0;
				}
				while(!Mechos.empty()) {
					int x = Mechos.front().first, y = Mechos.front().second; Mechos.pop();	
					if (dist[x][y] == S) {
						// cout << x << " " << y << nl;
						last.push({x, y});
						continue;
					}			
					for (auto move: moves) {
						int nx = x + move.first, ny = y + move.second;
						//Siamo Mecho
						if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
						if (grid[nx][ny] == 0 || UsedMecho[nx][ny] || used[nx][ny]) continue;
						UsedMecho[nx][ny] = 1;
						dist[nx][ny] = dist[x][y] + 1;
						Mechos.push({nx, ny});
					}	
				}
				if (!last.empty()) q.push_back({1, last});
			} else {
				while(!myQ.empty()) {
					int x = myQ.front().first, y = myQ.front().second; myQ.pop();
					if (distBee[x][y] == minutes-1 && !MechoIn) {
						// for (int a=0; a<N; a++) {
						// 	for (int b=0; b<N; b++) {
						// 		cout << used[a][b] << " ";
						// 	}
						// 	cout << nl;
						// }
						MechoIn = 1;
						UsedMecho[Mecho.first][Mecho.second] = 1;
						queue<pair<int, int>> MechoQ;
						MechoQ.push({Mecho.first, Mecho.second});
						q.push_back({1, MechoQ});
					}
					for (auto move: moves) {
						int nx = x + move.first, ny = y + move.second;
						//Siamo le api
						if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
						if (grid[nx][ny] == 0 || grid[nx][ny] == 2 || used[nx][ny]) continue;
						used[nx][ny] = 1;
						distBee[nx][ny] = distBee[x][y] + 1;
						UsedMecho[nx][ny] = 1;
						last.push({nx, ny});
					}
				}
				if (!last.empty()) q.push_back({0, last});
			}
		}
		if (UsedMecho[Home.first][Home.second]) {
			a = minutes+1;
		}
		else b = minutes-1;
	} 
	cout << b << nl;
}

• Subtask 1: 25 / 100