Submission #1243720

#TimeUsernameProblemLanguageResultExecution timeMemory
1243720marcus06Mecho (IOI09_mecho)C++20
95 / 100
169 ms6864 KiB
#include <bits/stdc++.h> using namespace std; using lli = long long; /*How to use: Tvector <int, 2> g(n); //graph Tvector <int, 3> f(n, k, 2) = f[n][k][2] */ template <class Tp, int D = 1> struct Tvector : public vector<Tvector<Tp, D - 1>> { template <class... Args> Tvector(int n = 0, Args... args) : vector<Tvector<Tp, D - 1>>(n, Tvector<Tp, D - 1>(args...)) {} }; template <class Tp> struct Tvector<Tp, 1> : public vector<Tp> { Tvector(int n = 0, Tp val = Tp()) : vector<Tp>(n, val) {} }; #ifdef LOCAL #include </home/marcus06/CP/Library/debug.h> #else #define debug(...) #endif const int dx[] = {0, 0, -1, 1}; const int dy[] = {-1, 1, 0, 0}; void solve() { int n, s; cin >> n >> s; Tvector <char, 2> g(n, n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { cin >> g[i][j]; } } int h_x, h_y; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (g[i][j] == 'D') { h_x = i; h_y = j; } } } int m_x, m_y; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (g[i][j] == 'M') { m_x = i; m_y = j; } } } auto valid = [&](int x, int y) -> bool { return (x >= 0 && y >= 0 && x < n && y < n && (g[x][y] == 'G' || g[x][y] == 'M')); }; Tvector <int, 2> bee_dist(n, n); Tvector <bool, 2> bee_vis(n, n); { queue <pair <int, int>> q; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (g[i][j] == 'H') { bee_dist[i][j] = 0; bee_vis[i][j] = true; q.emplace(i, j); } } } while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (int i = 0; i < 4; ++i) { int u = x + dx[i], v = y + dy[i]; if (valid(u, v) && !bee_vis[u][v]) { bee_vis[u][v] = true; bee_dist[u][v] = bee_dist[x][y] + 1; q.emplace(u, v); } } } } Tvector <int, 2> Mecho_dist(n, n); Tvector <bool, 2> Mecho_vis(n, n); auto possible = [&](int t) -> bool { fill(Mecho_vis.begin(), Mecho_vis.end(), Tvector <bool, 1>(n, false)); queue <pair <int, int>> q; q.emplace(m_x, m_y); Mecho_dist[m_x][m_y] = 0; if (bee_dist[m_x][m_y] <= t) q.pop(); while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (int i = 0; i < 4; ++i) { int u = x + dx[i], v = y + dy[i]; if (valid(u, v) && !Mecho_vis[u][v]) { int nxt_dist = t + (Mecho_dist[x][y] + 1) / s; if (nxt_dist < bee_dist[u][v]) { Mecho_vis[u][v] = true; Mecho_dist[u][v] = Mecho_dist[x][y] + 1; q.emplace(u, v); } } } } bool is_success = false; for (int i = 0; i < 4; ++i) { int u = h_x + dx[i], v = h_y + dy[i]; if (valid(u, v) && Mecho_vis[u][v]) { if (t + Mecho_dist[u][v] / s < bee_dist[u][v]) is_success = true; } } return is_success; }; int l = -1, r = int(1e9); while (r - l > 1) { int mid = (l + r) / 2; if (possible(mid)) l = mid; else r = mid; } if (!possible(0)) l = -1; cout << l << '\n'; } int main() { std::cin.tie(0)->sync_with_stdio(0); #ifdef LOCAL auto begin = std::chrono::high_resolution_clock::now(); #endif int tt = 1; while (tt--) { solve(); } #ifdef LOCAL auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); std::cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; #endif return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...