Submission #513899

#	Time	Username	Problem	Language	Result	Execution time	Memory
513899		nhuang685	Mecho (IOI09_mecho)	C++17	100 / 100	201 ms	6724 KiB

mecho

#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);
      |     ^~~

• Subtask 1: 100 / 100