# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
513899 | nhuang685 | Mecho (IOI09_mecho) | C++17 | 201 ms | 6724 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 <bits/stdc++.h>
#ifdef VSLOCAL
#include "debug/d.h"
#endif
#ifdef LOCAL
// Don't use this for USACO
#include "../../debug/d.h"
#endif
using namespace std;
using ll = long long;
using ld = long double;
#if defined(LOCAL) || defined(VSLOCAL)
#define dbg(...) line_info(__LINE__, #__VA_ARGS__), dbg1(__VA_ARGS__)
void nline() { cerr << '\n'; }
#else
#define dbg(...) 0
void nline() {}
#endif
int main() {
ios::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("log.txt", "w", stderr);
#endif
const array<int, 4> dx {-1, 0, 1, 0}, dy {0, 1, 0, -1};
// int N, S;
int N; ll S;
cin >> N >> S;
vector<vector<char>> grid (N, vector<char> (N));
queue<pair<ll, pair<int, int>>> q;
vector<vector<ll>> beetime (N, vector<ll> (N, (ll)4e18));
vector<vector<bool>> visited (N, vector<bool> (N));
pair<int, int> honey, home;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
cin >> grid[i][j];
if (grid[i][j] == 'H') {
q.push({0, {i, j}});
visited[i][j] = true;
beetime[i][j] = 0;
}
else if (grid[i][j] == 'M') honey = {i, j};
else if (grid[i][j] == 'D') home = {i, j};
}
}
while (!q.empty()) {
auto [dist, loc] = q.front();
q.pop();
for (int d = 0; d < 4; ++d) {
pair<int, int> nloc = {loc.first + dx[d], loc.second + dy[d]};
if (nloc.first < 0 || nloc.first >= N || nloc.second < 0 || nloc.second >= N || visited[nloc.first][nloc.second]) continue;
if (grid[nloc.first][nloc.second] == 'G' || grid[nloc.first][nloc.second] == 'M') {
visited[nloc.first][nloc.second] = true;
beetime[nloc.first][nloc.second] = dist + S;
q.push({dist + S, nloc});
}
}
}
dbg(beetime);
auto good = [&](ll val) {
visited.assign(N, vector<bool> (N));
visited[honey.first][honey.second] = true;
queue<pair<ll, pair<int, int>>> q;
q.push({val * S, honey});
if (val * S >= beetime[honey.first][honey.second]) return false;
while (!q.empty()) {
auto [dist, loc] = q.front();
q.pop();
for (int d = 0; d < 4; ++d) {
pair<int, int> nloc = {loc.first + dx[d], loc.second + dy[d]};
if (nloc.first < 0 || nloc.first >= N || nloc.second < 0 || nloc.second >= N
|| visited[nloc.first][nloc.second] || dist + 1 >= beetime[nloc.first][nloc.second]) continue;
if (grid[nloc.first][nloc.second] == 'D') {
return true;
}
else if (grid[nloc.first][nloc.second] == 'G') {
visited[nloc.first][nloc.second] = true;
q.push({dist + 1, nloc});
}
}
}
return false;
};
ll low = 0, high = 1e16;
while (low < high) {
ll mid = (low + high + 1) / 2;
if (good(mid)) low = mid;
else high = mid - 1;
}
if (good(low)) cout << low << '\n';
else cout << "-1\n";
// cout << "-1\n";
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |