Submission #1324226

#	Time	Username	Problem	Language	Result	Execution time	Memory
1324226		sh_qaxxorov_571	Mecho (IOI09_mecho)	C++20	84 / 100	168 ms	6184 KiB

mecho

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

using namespace std;

int N, S;
int startX, startY, homeX, homeY;
int bees[805][805];
char grid[805][805];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

bool check(int waitTime) {
    if (bees[startX][startY] <= waitTime) return false;
    
    vector<vector<int>> mechoDist(N, vector<int>(N, -1));
    queue<pair<int, int>> q;
    
    q.push({startX, startY});
    mechoDist[startX][startY] = 0;
    
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        if (x == homeX && y == homeY) return true;
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < N && ny >= 0 && ny < N && 
                (grid[nx][ny] == 'G' || grid[nx][ny] == 'D') && mechoDist[nx][ny] == -1) {
                
                int nextDist = mechoDist[x][y] + 1;
                // Mecho yetib borgan vaqtda asalarilar u yerda bo'lmasligi kerak
                if (waitTime + nextDist / S < bees[nx][ny]) {
                    mechoDist[nx][ny] = nextDist;
                    q.push({nx, ny});
                }
            }
        }
    }
    return false;
}

int main() {
    cin >> N >> S;
    queue<pair<int, int>> beeQ;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> grid[i][j];
            bees[i][j] = 1e9;
            if (grid[i][j] == 'H') {
                beeQ.push({i, j});
                bees[i][j] = 0;
            } else if (grid[i][j] == 'M') {
                startX = i; startY = j;
            } else if (grid[i][j] == 'D') {
                homeX = i; homeY = j;
            }
        }
    }

    // 1. Asalarilar BFS
    while (!beeQ.empty()) {
        int x = beeQ.front().first;
        int y = beeQ.front().second;
        beeQ.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < N && ny >= 0 && ny < N && grid[nx][ny] == 'G' && bees[nx][ny] == 1e9) {
                bees[nx][ny] = bees[x][y] + 1;
                beeQ.push({nx, ny});
            }
        }
    }

    // 2. Binar qidiruv
    int low = 0, high = N * N, ans = -1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (check(mid)) {
            ans = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    cout << ans << endl;
    return 0;
}

• Subtask 1: 84 / 100