Submission #1175634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175634		superauto	Mecho (IOI09_mecho)	C++20	4 / 100	64 ms	6260 KiB

mecho

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Cell {
    int x, y, time;
};

int N, S;
vector<string> forest;
vector<vector<int>> beeTime, mechoTime;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void bfsBees(queue<Cell>& q) {
    while (!q.empty()) {
        Cell cell = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nx = cell.x + dx[d], ny = cell.y + dy[d];
            if (nx >= 0 && nx < N && ny >= 0 && ny < N && forest[nx][ny] == 'G' && beeTime[nx][ny] == -1) {
                beeTime[nx][ny] = cell.time + 1;
                q.push({nx, ny, cell.time + 1});
            }
        }
    }
}

bool canMechoSurvive(int waitTime, pair<int, int> start, pair<int, int> home) {
    queue<Cell> q;
    q.push({start.first, start.second, 0});
    mechoTime.assign(N, vector<int>(N, -1));
    mechoTime[start.first][start.second] = 0;
    
    while (!q.empty()) {
        Cell cell = q.front(); q.pop();
        if (cell.x == home.first && cell.y == home.second) return true;
        
        for (int d = 0; d < 4; d++) {
            int nx = cell.x + dx[d], ny = cell.y + dy[d];
            if (nx >= 0 && nx < N && ny >= 0 && ny < N && forest[nx][ny] != 'T' && forest[nx][ny] != 'H' && mechoTime[nx][ny] == -1) {
                int reachTime = cell.time + 1;
                if (reachTime * S < beeTime[nx][ny] - waitTime) {
                    mechoTime[nx][ny] = reachTime;
                    q.push({nx, ny, reachTime});
                }
            }
        }
    }
    return false;
}

int main() {
    cin >> N >> S;
    forest.resize(N);
    beeTime.assign(N, vector<int>(N, -1));
    queue<Cell> bees;
    pair<int, int> mecho, home;
    
    for (int i = 0; i < N; i++) {
        cin >> forest[i];
        for (int j = 0; j < N; j++) {
            if (forest[i][j] == 'M') mecho = {i, j};
            else if (forest[i][j] == 'D') home = {i, j};
            else if (forest[i][j] == 'H') {
                bees.push({i, j, 0});
                beeTime[i][j] = 0;
            }
        }
    }
    
    bfsBees(bees);
    
    int left = 0, right = N * N, answer = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (canMechoSurvive(mid, mecho, home)) {
            answer = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    cout << answer << endl;
    return 0;
}

• Subtask 1: 4 / 100