IOI 2009 - Mecho

Official Analysis

Explanation

Assuming that Mecho can reach his cave before the bees, it is guaranteed that Mecho can do this if he eats for any time between 0 and x. Any time greater than x would allow the bees to catch Mecho.

From this observation, we find out that we can binary search on the eating time to find the latest possible time Mecho can leave. For time x, which is the amount of time Mecho eats for, we check if Mecho can reach his cave before the bees. If he can, then binary search on times greater than x, otherwise, binary search on times smaller than x. Do this until a single eating time is left. To see if Mecho can reach his cave before the bees, he needs to have a path on which every square is a grassy patch, and is reachable by Mecho before the bees.

Run one BFS for the bees, and record the time taken for the bees to reach every possible node in the graph.Then run another BFS for Mecho, where a node will only be visited by Mecho if it is a grassy patch and the bees took more time reach the node than Mecho. If both these conditions are fulfilled, then we can say that Mecho reached the node before the bees. At the end of the BFS, check if Mecho reached any of the four nodes surrounding his cave. If he did, then Mecho successfully reached the cave while eating for x time. Otherwise, Mecho will have to eat for less than x time.

Output the maximum waiting time found out by the binary search. If Mecho cannot reach the cave even when he ate for 0 units of time, then there is no path from his starting position to the cave. In this case, output -1.

Implementation

Time Complexity: $\mathcal{O}(N^2\log N)$

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

const int MAX_N = 800;
vector<string> field(MAX_N);
int n, s;

bool valid_sq(int x, int y) {
	return x >= 0 && x < n && y >= 0 && y < n &&
	       (field[x][y] == 'G' || field[x][y] == 'M');