# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
888542 | Billy_Nguyen | Mecho (IOI09_mecho) | C++17 | 124 ms | 27680 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pair<int, int>> vpi;
#define x first
#define fastio() \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0)
#define y second
#define PB push_back
#define MP make_pair
#define REP(i, a, b) for (int i = a; i < b; i++)
int mod = 1e9 + 7;
int mod_inverse_2 = 500000004; // Modular inverse of 2 modulo (10^9 + 7), also
// the number has to be in long long otherwise
// if the number is int need to mutiply by 1LL
const int N = 100009;
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
ll bound = 1e18;
vector<vector<char>> grid;
ll n, s;
pair<ll, ll> bear, home;
vector<pair<ll, ll>> hives;
vector<vector<ll>> beesDepths;
vector<vector<ll>> bearDepths;
bool valid = false;
void floodfill(ll i, ll j, vector<vector<bool>> &visited, ll mins) {
REP(k, 0, 4) {
if (i + dy[k] < 1 || j + dx[k] < 1 || i + dy[k] > n || j + dx[k] > n) {
continue;
}
if (visited[i + dy[k]][j + dx[k]]) {
continue;
}
if ((bearDepths[i + dy[k]][j + dx[k]] + 1) / s >=
beesDepths[i + dy[k]][j + dx[k]] - mins) {
continue;
}
if (grid[i + dy[k]][j + dx[k]] == 'D') {
valid = true;
return;
}
if (grid[i + dy[k]][j + dx[k]] != 'G') {
continue;
}
visited[i][j] = true;
floodfill(i + dy[k], j + dx[k], visited, mins);
}
}
void solve() {
cin >> n >> s;
grid.resize(n + 1);
beesDepths.resize(n + 1);
REP(i, 0, n + 1) {
grid[i].resize(n + 1);
beesDepths[i].resize(n + 1, 1e18);
}
REP(i, 1, n + 1) {
REP(j, 1, n + 1) {
cin >> grid[i][j];
if (grid[i][j] == 'M') {
bear = {i, j};
}
if (grid[i][j] == 'D') {
home = {i, j};
}
if (grid[i][j] == 'H') {
hives.PB({i, j});
}
}
}
deque<pair<pair<ll, ll>, ll>> q;
REP(i, 0, hives.size()) {
q.PB(MP(hives[i], 0));
beesDepths[hives[i].x][hives[i].y] = 0;
}
while (!q.empty()) {
pair<pair<ll, ll>, ll> cur = q.front();
pair<ll, ll> coords = cur.x;
ll d = cur.y;
q.pop_front();
REP(k, 0, 4) {
if (coords.x + dy[k] < 1 || coords.y + dx[k] < 1 ||
coords.x + dy[k] > n || coords.y + dy[k] > n ||
(grid[coords.x + dy[k]][coords.y + dx[k]] != 'G' &&
grid[coords.x + dy[k]][coords.y + dx[k]] != 'D' && grid[coords.x + dy[k]][coords.y + dx[k]] != 'M')) {
continue;
}
if (beesDepths[coords.x + dy[k]][coords.y + dx[k]] > d + 1) {
beesDepths[coords.x + dy[k]][coords.y + dx[k]] = d + 1;
q.PB(MP(MP(coords.x + dy[k], coords.y + dx[k]), d + 1));
}
}
}
ll l = 0;
ll r = n * n;
q.PB(MP(bear, 0));
bearDepths.resize(n + 1);
REP(i, 0, n + 1) { bearDepths[i].resize(n + 1, 1e18); }
bearDepths[bear.x][bear.y] = 0;
while (!q.empty()) {
pair<pair<ll, ll>, ll> cur = q.front();
q.pop_front();
pair<ll, ll> coords = cur.x;
ll d = cur.y;
REP(k, 0, 4) {
if (coords.x + dy[k] < 1 || coords.y + dx[k] < 1 ||
coords.x + dy[k] > n || coords.y + dy[k] > n ||
(grid[coords.x + dy[k]][coords.y + dx[k]] != 'G' &&
grid[coords.x + dy[k]][coords.y + dx[k]] != 'D')) {
continue;
}
if (bearDepths[coords.x + dy[k]][coords.y + dx[k]] > d + 1) {
bearDepths[coords.x + dy[k]][coords.y + dx[k]] = d + 1;
q.PB(MP(MP(coords.x + dy[k], coords.y + dx[k]), d + 1));
}
}
}
while (l <= r) {
ll mid = l + (r - l) / 2;
vector<vector<bool>> bearVis(n + 1);
REP(i, 0, n + 1) { bearVis[i].resize(n + 1, false); }
bearVis[bear.x][bear.y] = true;
floodfill(bear.x, bear.y, bearVis, mid);
if (valid) {
l = mid + 1;
} else {
r = mid - 1;
}
// cout << l << " " << r << "\n";
}
cout << l - 1 << "\n";
}
int main() {
fastio();
solve();
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |