Submission #1020302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020302		niwrad	Mecho (IOI09_mecho)	C++17	100 / 100	146 ms	8732 KiB

mecho

#include <bits/stdc++.h>
using namespace std;


int r_c[]{0, 1, 0, -1};
int c_c[]{1, 0, -1, 0};
int n, s;
vector<vector<int>> arr;
int r_s, c_s;
int r_f, c_f;
queue<pair<int, int>> hives;
vector<vector<int>> dis;


void fill() {
    while (hives.size() != 0) {
        pair<int, int> t = hives.front();
        for (int i = 0; i < 4; i++) {
            int n_r = t.first + r_c[i];
            int n_c = t.second + c_c[i];
            if (min(n_r, n_c) >= 0 && max(n_r, n_c) < n) {
                if (arr[n_r][n_c] == 0 && dis[n_r][n_c] == -1) {
                    dis[n_r][n_c] = dis[t.first][t.second] + 1;
                    hives.push({n_r, n_c});
                }
            }
        }
        hives.pop();
    }
}

bool check(int time) {
    vector<vector<int>> len(n, vector<int>(n));
    queue<pair<int, int>> q;
    q.push({r_s, c_s});
    while (q.size() != 0) {
        pair<int, int> t = q.front();
        for (int i = 0; i < 4; i++) {
            int n_r = t.first + r_c[i];
            int n_c = t.second + c_c[i];
            if (min(n_r, n_c) >= 0 && max(n_r, n_c) < n) {
                if (arr[n_r][n_c] != -1 && len[n_r][n_c] == 0) {
                    if (dis[n_r][n_c] == -1 || (1 + len[t.first][t.second]) / s + time < dis[n_r][n_c]) {
                        len[n_r][n_c] = 1 + len[t.first][t.second];
                        q.push({n_r, n_c});
                    }
                }
            }
        }
        q.pop();
    }
    if (len[r_f][c_f] != 0) {
        return true;
    } else {
        return false;
    }
}




int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> s;
    arr.resize(n, vector<int>(n));
    dis.resize(n, vector<int>(n, -1));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            char c;
            cin >> c;
            if (c == 'T') {
                arr[i][j] = -1;
            } else if (c == 'M') {
                r_s = i; c_s = j;
            } else if (c == 'D') {
                arr[i][j] = 1;
                r_f = i; c_f = j;
            } else if (c == 'H') {
                dis[i][j] = 0;
                hives.push({i, j});
            }
        }
    }
    fill();
    if (!check(0)) {
        cout << "-1\n";
    } else {
        int l = 0;
        int r = dis[r_s][c_s];
        while (r > l + 1) {
            int m = (l + r) / 2;
            if (check(m)) {
                l = m;
            } else {
                r = m;
            }
        }
        cout << l << "\n";
    }
}

• Subtask 1: 100 / 100