Submission #907251

#	Time	Username	Problem	Language	Result	Execution time	Memory
907251		Ghetto	Mecho (IOI09_mecho)	C++17	100 / 100	300 ms	7768 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAX_N = 800 + 5, INF = 1e9, MAX_T = MAX_N * MAX_N;

int n, s;
char arr[MAX_N][MAX_N];

bool bee_seen[MAX_N][MAX_N];
int bee_dist[MAX_N][MAX_N]; // INF if unreachable
queue<pii> bee_order;
void bee_bfs() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            if (arr[i][j] == 'H') {
                bee_seen[i][j] = true;
                bee_order.push({i, j});
            } else
                bee_dist[i][j] = INF;
    }
        
    while (bee_order.size()) {
        int i = bee_order.front().first, j = bee_order.front().second;
        bee_order.pop();

        vector<pii> delta = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (pii in : delta) {
            int new_i = i + in.first, new_j = j + in.second;
            if (new_i < 1 || new_i > n || new_j < 1 || new_j > n) continue;
            if (arr[new_i][new_j] == 'T' || arr[new_i][new_j] == 'D') continue;
            if (bee_seen[new_i][new_j]) continue;

            bee_seen[new_i][new_j] = true;
            bee_dist[new_i][new_j] = bee_dist[i][j] + 1;
            bee_order.push({new_i, new_j});
        }
    }
}

bool check_seen[MAX_N][MAX_N];
int check_dist[MAX_N][MAX_N]; // INF if unreachable
queue<pii> check_order;
bool check(int t) {
    pii finish = {0, 0};
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (arr[i][j] == 'M') {
                if (bee_dist[i][j] < t) return false;

                check_seen[i][j] = true;
                check_dist[i][j] = 0;
                check_order.push({i, j});
            } else {
                check_seen[i][j] = false;
                check_dist[i][j] = INF;
            }
            if (arr[i][j] == 'D')
                finish = {i, j};
        }
    }
    
    while (check_order.size()) {
        int i = check_order.front().first, j = check_order.front().second;
        check_order.pop();

        // cout << t << ": " << i << " " << j << endl;

        vector<pii> delta = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (pii in : delta) {
            int new_i = i + in.first, new_j = j + in.second;
            if (new_i < 1 || new_i > n || new_j < 1 || new_j > n) continue;
            if (arr[new_i][new_j] == 'T') continue;
            if (check_seen[new_i][new_j]) continue;

            int new_dist = check_dist[i][j] + 1;
            if (bee_dist[new_i][new_j] < t + (new_dist / s)) continue;
            check_dist[new_i][new_j] = new_dist;

            check_seen[new_i][new_j] = true;
            check_order.push({new_i, new_j}); 
        }
    }

    return check_seen[finish.first][finish.second];
}
int bin_search() {
    int lo = 1, hi = MAX_T;
    while (lo != hi) {
        int mid = ceil((lo + hi) / (double) 2);
        if (check(mid)) lo = mid;
        else hi = mid - 1;
    }
    if (check(lo)) return lo;
    else return -1;
}

int main() {
    // freopen("mecho.in", "r", stdin);

    cin >> n >> s;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> arr[i][j];
    
    bee_bfs();

    int ans = bin_search();
    if (ans != -1) ans--;
    cout << ans << '\n';

    // for (int i = 1; i <= n; i++) {
    //     for (int j = 1; j <= n; j++)
    //         cout << bee_dist[i][j] << " ";
    //     cout << endl;
    // }
        
}

• Subtask 1: 100 / 100