Submission #406413

#TimeUsernameProblemLanguageResultExecution timeMemory
406413FalconMecho (IOI09_mecho)C++17
84 / 100
242 ms6960 KiB
#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)

mecho.cpp: In function 'int main()':
mecho.cpp:33:29: warning: statement has no effect [-Wunused-value]
   33 | #define debug(x...)         42
      |                             ^~
mecho.cpp:120:5: note: in expansion of macro 'debug'
  120 |     debug(bee_dist);
      |     ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...