제출 #406421

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
406421		Falcon	Mecho (IOI09_mecho)	C++17	100 / 100	252 ms	6252 KiB

mecho

#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)
                return;
            
            if(grid[x][y] != 'G' && grid[x][y] != 'M')
                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') {
            if(~bee_dist[i][j] && bee_dist[i][j] <= t)
                return false;
            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;
     };

    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;
}

• Subtask 1: 100 / 100