# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
747793 | AverageAmogusEnjoyer | Mecho (IOI09_mecho) | C++17 | 742 ms | 6592 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define pb push_back
#define ll long long
#define nl '\n'
/*
Mecho can only walk on grass and cannot go through trees or hives, and he can make at most S steps per minute.
every minute
he eats or
he leaves immediately and takes up to S steps through the forest as described above
bees spread to grassy cells
trees = no one can go there
m = mecho, grassy cells => i will replace with g
g = grassy
d = mecho home; bees cannot go / pass here
h = hive
*/
const int N = 810;
char grid[N][N];
int stepsMecho[N][N], stepsBee[N][N];
int n, s;
array<int, 2> Mecho, MechoHouse;
vector<array<int, 2>> Bee;
vector<array<int,2>> moves = {{-1,0},{1,0},{0,-1},{0,1}};
struct m{
bool isMecho;
int x,y;
};
bool good(int x, int y) {
return 0 <= x && x < n && 0 <= y && y < n && grid[x][y] != 'T';
}
bool isHome(int x, int y) {
return x == MechoHouse[0] && y == MechoHouse[1];
}
void debug() {
cout << "Mecho: " << nl;
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) {
cout << stepsMecho[i][j] << " ";
}
cout << nl;
}
cout << "Bees: " << nl;
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) {
cout << stepsBee[i][j] << " ";
}
cout << nl;
}
}
bool bs(int steps) {
memset(stepsMecho,-1,sizeof(stepsMecho));
memset(stepsBee,-1,sizeof(stepsBee));
queue<m> q, q2;
q2.push(m{true,Mecho[0],Mecho[1]});
stepsMecho[Mecho[0]][Mecho[1]] = 0;
for (auto [x,y]:Bee) {
q.push(m{false,x,y});
stepsBee[x][y]=0;
}
while(!q.empty()) {
m v = q.front(); q.pop();
if (stepsBee[v.x][v.y] == steps) { q2.push(v); continue; }
for (auto [addx,addy]: moves) {
int nx = v.x + addx, ny = v.y + addy;
if (good(nx,ny) && !isHome(nx,ny) && stepsBee[nx][ny] == -1) {
q.push(m{false,nx,ny});
stepsBee[nx][ny] = stepsBee[v.x][v.y]+1;
}
}
}
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
if (stepsBee[i][j] != -1)
stepsBee[i][j] = 0;
while(!q2.empty()) {
m v = q2.front(); q2.pop();
if (v.isMecho) {
if (stepsBee[v.x][v.y] != -1 && stepsBee[v.x][v.y] <= (stepsMecho[v.x][v.y]+s-1)/s) { continue; }
for (auto [addx,addy]: moves) {
int nx = v.x + addx, ny = v.y + addy;
if (good(nx,ny) && stepsMecho[nx][ny] == -1 && (stepsBee[nx][ny] == -1 || stepsBee[nx][ny] > (stepsMecho[v.x][v.y]+s)/s)) {
if (isHome(nx,ny)) { return 1; }
stepsMecho[nx][ny] = stepsMecho[v.x][v.y]+1;
q2.push(m{true,nx,ny});
}
}
} else {
for (auto [addx,addy]: moves) {
int nx = v.x + addx, ny = v.y + addy;
if (good(nx,ny) && !isHome(nx,ny) && stepsBee[nx][ny] == -1) {
q2.push(m{false,nx,ny});
stepsBee[nx][ny] = stepsBee[v.x][v.y]+1;
}
}
}
}
return 0;
}
signed main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> s;
for (int i=0;i<n;i++)
for (int j=0;j<n;j++) {
cin >> grid[i][j];
if (grid[i][j]=='M') {
grid[i][j] = 'G';
Mecho = {i,j};
}
if (grid[i][j]=='H') {
Bee.pb({i,j});
}
if (grid[i][j]=='D') {
MechoHouse = {i,j};
}
}
int lo = 0, hi = 1e9;
while(lo<=hi) {
int mid = (lo+hi)/2;
if (bs(mid)) {
lo = mid + 1;
} else {
if (mid==0) {
cout << -1;
return 0;
}
hi = mid - 1;
}
}
cout << lo;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |