Submission #513899

#TimeUsernameProblemLanguageResultExecution timeMemory
513899nhuang685Mecho (IOI09_mecho)C++17
100 / 100
201 ms6724 KiB
#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)

mecho.cpp: In function 'int main()':
mecho.cpp:19:18: warning: statement has no effect [-Wunused-value]
   19 | #define dbg(...) 0
      |                  ^
mecho.cpp:69:5: note: in expansion of macro 'dbg'
   69 |     dbg(beetime);
      |     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...