# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
406413 | Falcon | Mecho (IOI09_mecho) | C++17 | 242 ms | 6960 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 DEBUG
#include "debug.hpp"
#endif
using namespace std;
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); ++it)
#define rep(i, N) for(int i = 0; i < (N); ++i)
#define rrep(i, N) for(int i = (N) - 1; i >= 0; --i)
#define rep1(i, N) for(int i = 1; i <= (N); ++i)
#define rep2(i, s, e) for(int i = (s); i <= (e); ++i)
#ifdef DEBUG
#define debug(x...) { \
++dbg::depth; \
string dbg_vals = dbg::to_string(x); \
--dbg::depth; \
dbg::fprint(__func__, __LINE__, #x, dbg_vals); \
}
#define light_debug(x) { \
dbg::light = true; \
dbg::dout << __func__ << ":" << __LINE__; \
dbg::dout << " " << #x << " = " << x << endl; \
dbg::light = false; \
}
#else
#define debug(x...) 42
#define light_debug(x) 42
#endif
using ll = long long;
template<typename T>
inline T& ckmin(T& a, T b) { return a = a > b ? b : a; }
template<typename T>
inline T& ckmax(T& a, T b) { return a = a < b ? b : a; }
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, s; cin >> n >> s;
vector<string> grid(n); rep(i, n) cin >> grid[i];
vector<vector<int>> bee_dist = [&]{
vector<vector<int>> dist(n, vector<int>(n, -1));
queue<pair<int, int>> q;
rep(i, n) rep(j, n) if(grid[i][j] == 'H')
q.push({i, j}), dist[i][j] = 0;
auto add = [&](int x, int y, int d) {
if(x < 0 || y < 0 || x >= n || y >= n || grid[x][y] != 'G')
return;
if(~dist[x][y])
return;
q.push({x, y});
dist[x][y] = d + s;
};
while(!q.empty()) {
auto [i, j] = q.front(); q.pop();
add(i + 1, j, dist[i][j]);
add(i, j + 1, dist[i][j]);
add(i - 1, j, dist[i][j]);
add(i, j - 1, dist[i][j]);
}
return dist;
}();
auto check = [&](int t) {
t = t * s;
queue<pair<int, int>> q;
vector<vector<int>> dist(n, vector<int>(n, -1));
rep(i, n) rep(j, n) if(grid[i][j] == 'M')
q.push({i, j}), dist[i][j] = t;
auto add = [&](int x, int y, int d) {
if(x < 0 || y < 0 || x >= n || y >= n)
return;
if(grid[x][y] != 'G' && grid[x][y] != 'D')
return;
if(~dist[x][y])
return;
if(~bee_dist[x][y] && d + 1 >= bee_dist[x][y])
return;
q.push({x, y});
dist[x][y] = d + 1;
};
while(!q.empty()) {
auto [i, j] = q.front(); q.pop();
if(grid[i][j] == 'D')
return true;
add(i + 1, j, dist[i][j]);
add(i - 1, j, dist[i][j]);
add(i, j + 1, dist[i][j]);
add(i, j - 1, dist[i][j]);
}
return false;
};
debug(bee_dist);
if(!check(0))
return cout << -1 << '\n', 0;
int t{};
for(int k{1 << __lg(n * n)}; k > 0; k >>= 1)
if(t + k <= n * n && check(t + k))
t += k;
cout << t << '\n';
#ifdef DEBUG
dbg::dout << "\nExecution time: "
<< clock() * 1000 / CLOCKS_PER_SEC
<< "ms" << endl;
#endif
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |