제출 #581559

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
581559		Saeed_247	Mecho (IOI09_mecho)	C++17	100 / 100	733 ms	6744 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
template<typename T> void dout(string name, T arg) {
    cerr << name << " = " << arg << "\e[39m" << endl;
}
template<typename T1, typename... T2> void dout(string names, T1 arg, T2... args) {
    cerr << names.substr(0, names.find(',')) << " = " << arg << " | ";
    dout(names.substr(names.find(',') + 2), args...);
}
#define debug(...) cerr << "\e[91m" << "[" << __LINE__ << ":" << __func__ << "]=> ", dout(#__VA_ARGS__,  __VA_ARGS__);

const int N = 800;
vector<string> field(N);
int n, s;

bool valid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n && (field[x][y] == 'G' || field[x][y] == 'M');
}

bool reached(int m, int b) {
    return m / s < b;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> s;
    for (int i = 0; i < n; i++) {
        cin >> field[i];
    }

    vector<pair<int, int>> hives;
    pair<int, int> m, d;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (field[i][j] == 'M') {
                m = {i, j};
            }
            if (field[i][j] == 'H') {
                hives.push_back({i, j});
            }
            if (field[i][j] == 'D') {
                d = {i, j};
            }
        }
    }

    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, -1, 0, 1};

    int l = 0, r = n * n;
    while (l <= r) {
        vector<vector<bool>> bees_visited(n, vector<bool>(n));
		vector<vector<bool>> mecho_visited(n, vector<bool>(n));
		vector<vector<int>> bees_time(n, vector<int>(n));
		vector<vector<int>> mecho_time(n, vector<int>(n));
		queue<pair<int, int>> q;
        int mid = (l + r) / 2;

        for (auto [x, y] : hives) {
            q.push({x, y});
            bees_visited[x][y] = true;
        }
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            for (int i = 0; i < 4; i++) {
                int xx = x + dx[i], yy = y + dy[i];
                if (valid(xx, yy) && !bees_visited[xx][yy]) {
                    bees_time[xx][yy] = bees_time[x][y] + 1;
                    q.push({xx, yy});
                    bees_visited[xx][yy] = true;
                }
            }
        }

        q.push(m);
        mecho_visited[m.first][m.second] = true;
        if (bees_time[m.first][m.second] <= mid) {
            q.pop();
        }
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            for (int i = 0; i < 4; i++) {
                int xx = x + dx[i], yy = y + dy[i];
                if (valid(xx, yy) && !mecho_visited[xx][yy] && reached(mecho_time[x][y] + 1, bees_time[xx][yy] - mid)) {
                    mecho_time[xx][yy] = mecho_time[x][y] + 1;
                    q.push({xx, yy});
                    mecho_visited[xx][yy] = true;
                }
            }
        }

        bool reach = false;
        for (int i = 0; i < 4; i++) {
            int xx = d.first + dx[i], yy = d.second + dy[i];
            if (valid(xx, yy) && reached(mecho_time[xx][yy], bees_time[xx][yy] - mid) && mecho_visited[xx][yy]) {
                reach = true;
            }
        }

        if (reach) {
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }
    cout << l - 1 << '\n';
    return 0;
}

• Subtask 1: 100 / 100