Submission #888542

#TimeUsernameProblemLanguageResultExecution timeMemory
888542Billy_NguyenMecho (IOI09_mecho)C++17
6 / 100
124 ms27680 KiB
#include <algorithm> #include <bitset> #include <cctype> #include <cmath> #include <cstring> #include <deque> #include <iomanip> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; typedef long long ll; typedef vector<int> vi; typedef pair<int, int> pi; typedef vector<pair<int, int>> vpi; #define x first #define fastio() \ ios::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0) #define y second #define PB push_back #define MP make_pair #define REP(i, a, b) for (int i = a; i < b; i++) int mod = 1e9 + 7; int mod_inverse_2 = 500000004; // Modular inverse of 2 modulo (10^9 + 7), also // the number has to be in long long otherwise // if the number is int need to mutiply by 1LL const int N = 100009; int dx[] = {0, 0, -1, 1}; int dy[] = {1, -1, 0, 0}; ll bound = 1e18; vector<vector<char>> grid; ll n, s; pair<ll, ll> bear, home; vector<pair<ll, ll>> hives; vector<vector<ll>> beesDepths; vector<vector<ll>> bearDepths; bool valid = false; void floodfill(ll i, ll j, vector<vector<bool>> &visited, ll mins) { REP(k, 0, 4) { if (i + dy[k] < 1 || j + dx[k] < 1 || i + dy[k] > n || j + dx[k] > n) { continue; } if (visited[i + dy[k]][j + dx[k]]) { continue; } if ((bearDepths[i + dy[k]][j + dx[k]] + 1) / s >= beesDepths[i + dy[k]][j + dx[k]] - mins) { continue; } if (grid[i + dy[k]][j + dx[k]] == 'D') { valid = true; return; } if (grid[i + dy[k]][j + dx[k]] != 'G') { continue; } visited[i][j] = true; floodfill(i + dy[k], j + dx[k], visited, mins); } } void solve() { cin >> n >> s; grid.resize(n + 1); beesDepths.resize(n + 1); REP(i, 0, n + 1) { grid[i].resize(n + 1); beesDepths[i].resize(n + 1, 1e18); } REP(i, 1, n + 1) { REP(j, 1, n + 1) { cin >> grid[i][j]; if (grid[i][j] == 'M') { bear = {i, j}; } if (grid[i][j] == 'D') { home = {i, j}; } if (grid[i][j] == 'H') { hives.PB({i, j}); } } } deque<pair<pair<ll, ll>, ll>> q; REP(i, 0, hives.size()) { q.PB(MP(hives[i], 0)); beesDepths[hives[i].x][hives[i].y] = 0; } while (!q.empty()) { pair<pair<ll, ll>, ll> cur = q.front(); pair<ll, ll> coords = cur.x; ll d = cur.y; q.pop_front(); REP(k, 0, 4) { if (coords.x + dy[k] < 1 || coords.y + dx[k] < 1 || coords.x + dy[k] > n || coords.y + dy[k] > n || (grid[coords.x + dy[k]][coords.y + dx[k]] != 'G' && grid[coords.x + dy[k]][coords.y + dx[k]] != 'D' && grid[coords.x + dy[k]][coords.y + dx[k]] != 'M')) { continue; } if (beesDepths[coords.x + dy[k]][coords.y + dx[k]] > d + 1) { beesDepths[coords.x + dy[k]][coords.y + dx[k]] = d + 1; q.PB(MP(MP(coords.x + dy[k], coords.y + dx[k]), d + 1)); } } } ll l = 0; ll r = n * n; q.PB(MP(bear, 0)); bearDepths.resize(n + 1); REP(i, 0, n + 1) { bearDepths[i].resize(n + 1, 1e18); } bearDepths[bear.x][bear.y] = 0; while (!q.empty()) { pair<pair<ll, ll>, ll> cur = q.front(); q.pop_front(); pair<ll, ll> coords = cur.x; ll d = cur.y; REP(k, 0, 4) { if (coords.x + dy[k] < 1 || coords.y + dx[k] < 1 || coords.x + dy[k] > n || coords.y + dy[k] > n || (grid[coords.x + dy[k]][coords.y + dx[k]] != 'G' && grid[coords.x + dy[k]][coords.y + dx[k]] != 'D')) { continue; } if (bearDepths[coords.x + dy[k]][coords.y + dx[k]] > d + 1) { bearDepths[coords.x + dy[k]][coords.y + dx[k]] = d + 1; q.PB(MP(MP(coords.x + dy[k], coords.y + dx[k]), d + 1)); } } } while (l <= r) { ll mid = l + (r - l) / 2; vector<vector<bool>> bearVis(n + 1); REP(i, 0, n + 1) { bearVis[i].resize(n + 1, false); } bearVis[bear.x][bear.y] = true; floodfill(bear.x, bear.y, bearVis, mid); if (valid) { l = mid + 1; } else { r = mid - 1; } // cout << l << " " << r << "\n"; } cout << l - 1 << "\n"; } int main() { fastio(); solve(); return 0; }

Compilation message (stderr)

mecho.cpp: In function 'void solve()':
mecho.cpp:32:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 | #define REP(i, a, b) for (int i = a; i < b; i++)
......
  109 |     REP(i, 0, hives.size()) {
      |         ~~~~~~~~~~~~~~~~~~              
mecho.cpp:109:5: note: in expansion of macro 'REP'
  109 |     REP(i, 0, hives.size()) {
      |     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...