Submission #1293761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293761		goppamach	Mecho (IOI09_mecho)	C++20	100 / 100	151 ms	6340 KiB

mecho

#include <bits/stdc++.h>

using namespace std;

#define el "\n"
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define FOR(i, l, r) for (int i = (l); i <= (r); i++)
#define FOD(i, l, r) for (int i = (l); i >= (r); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr);

using db = long double;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vbool = vector<bool>;
using vvbool = vector<vbool>;

template<class T> bool chmax(T &a, T const &b) { return (a < b ? (a = b, true) : false); }
template<class T> bool chmin(T &a, T const &b) { return (a > b ? (a = b, true) : false); }

// #define DEBUG
#ifdef DEBUG
#include "D:\cpp\debug.cpp"
#else
#define debug(...)
#define debug_arr(...)
#endif

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

constexpr int N = 805;
constexpr int INF = 1E9 + 7;
constexpr ll INFLL = 1E18;
constexpr int MOD = 1E9 + 7; // 998244353
constexpr double EPS = 1E-10;

char grid[N][N];
int bees_time[N][N], mecho_time[N][N];
int sx, sy, tx, ty;
int n, s;

const int directions[4][2] = {{-1, 0}, {+1, 0}, {0, -1}, {0, +1}};

bool valid_cell(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= n && grid[x][y] != 'T';
}

bool can_mecho_reach(int mecho_time, int bees_time) {
    return mecho_time / s < bees_time;
}

bool check(int delay) {
    memset(mecho_time, -1, sizeof mecho_time);
    queue<pii> q;
    q.emplace(sx, sy);
    mecho_time[sx][sy] = 0;
    if (bees_time[sx][sy] <= delay) q.pop();

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        if (x == tx && y == ty) return true;
        for (auto &[dx, dy] : directions) {
            int nx = x + dx, ny = y + dy;
            if (!valid_cell(nx, ny)) continue;
            if (mecho_time[nx][ny] == -1 && can_mecho_reach(mecho_time[x][y] + 1, bees_time[nx][ny] - delay)) {
                mecho_time[nx][ny] = mecho_time[x][y] + 1;
                q.emplace(nx, ny);
            }
        }
    }

    return false;
}

void solve() {
    cin >> n >> s;

    memset(bees_time, -1, sizeof bees_time);
    queue<pii> q;
    FOR(i, 1, n) {
        FOR(j, 1, n) {
            cin >> grid[i][j];
            if (grid[i][j] == 'M') {
                sx = i;
                sy = j;
            } else if (grid[i][j] == 'D') {
                tx = i;
                ty = j;
            } else if (grid[i][j] == 'H') {
                q.emplace(i, j);
                bees_time[i][j] = 0;
            }
        }
    }

    bees_time[tx][ty] = INF;
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (auto const &[dx, dy] : directions) {
            int nx = x + dx, ny = y + dy;
            if (!valid_cell(nx, ny)) continue;
            if (bees_time[nx][ny] == -1) {
                bees_time[nx][ny] = bees_time[x][y] + 1;
                q.emplace(nx, ny);
            }
        }
    }

    int l = 0, r = n * n, res = 0;
    while (l <= r) {
        int m = (l + r) / 2;
        if (check(m)) {
            res = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }

    cout << (!check(res) ? -1 : res) << el;
}

int main() {
    fast_io
    #define LOCAL
    #ifndef LOCAL
    #define PROBLEM ""
    freopen(PROBLEM ".INP", "r", stdin);
    freopen(PROBLEM ".OUT", "w", stdout);
    #endif

    int t = 1;
    // cin >> t;
    while (t--) solve();
}

• Subtask 1: 100 / 100