Submission #999666

#TimeUsernameProblemLanguageResultExecution timeMemory
999666a5a7Mecho (IOI09_mecho)C++14
100 / 100
191 ms11392 KiB
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template <class T> using indexedset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, s; cin >> n >> s; vector<vector<char>> grid(n, vector<char>(n)); queue<pair<ll, pair<int, int>>> h; pair<int, int> m; pair<int, int> dest; vector<pair<int, int>> dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; vector<vector<ll>> dist(n, vector<ll>(n, 1e9)); for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++){ cin >> grid[i][j]; if (grid[i][j] == 'H'){ h.push({0, {i, j}}); dist[i][j] = 0; } if (grid[i][j] == 'M'){ m = {i, j}; } if (grid[i][j] == 'D'){ dest = {i, j}; } } } while (!h.empty()){ int x = h.front().second.first; int y = h.front().second.second; ll d = h.front().first; h.pop(); if (dist[x][y] != d) continue; for (auto ne : dir){ int nx = x + ne.first; int ny = y + ne.second; if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue; if ((grid[nx][ny] == 'G' || grid[nx][ny] == 'M') && dist[nx][ny] > (d+1)){ h.push({d+1, {nx, ny}}); dist[nx][ny] = d+1; } } } function<bool(int)> works = [&](ll t){ queue<pair<ll, pair<int, int>>> q; vector<vector<ll>> di(n, vector<ll>(n, 1e9)); if ((dist[m.first][m.second]-t) <= 0){ return false; } di[m.first][m.second] = 0; q.push({0, m}); while (!q.empty()){ int x = q.front().second.first; int y = q.front().second.second; ll d = q.front().first; q.pop(); if (di[x][y] != d) continue; for (auto ne : dir){ int nx = x + ne.first; int ny = y + ne.second; if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue; if ((grid[nx][ny] == 'G' || grid[nx][ny] == 'D') && di[nx][ny] > (d+1) && (d+1) < s*(-t+dist[nx][ny])){ q.push({d+1, {nx, ny}}); di[nx][ny] = d+1; } } } if (di[dest.first][dest.second] == 1e9){ return false; } return true; }; ll l = -1, r = n*n; while (l < r){ ll m = (l+r+1)/2; if (works(m)){ l = m; }else{ r = m-1; } } cout << l << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...