Submission #1122498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122498		usacocamp	Mecho (IOI09_mecho)	C++20	16 / 100	151 ms	6344 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n';
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;

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

int n, s;
char grid[800][800];
int dist[800][800];
int path[800][800];
vector<pair<int, int>> hives;
pair<int, int> start;
pair<int, int> home;

bool inside(int i, int j) {
    if (i >= 0 && i < n && j >= 0 && j < n) {
        return true;
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> s;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j <  n;j++) {
            dist[i][j] = 1e9;
            cin >> grid[i][j];
            if (grid[i][j] == 'H') {
                hives.push_back({i, j});
            } else if (grid[i][j] == 'M') {
                start = {i, j};
            } else if (grid[i][j] == 'D') {
                home = {i, j};
            }
        }
    }
    queue<pair<int, int>> q;
    for (auto x : hives) {
        q.push(x);
        dist[x.first][x.second] = 0;
    }
    while (!q.empty()) {
        pair<int, int> s = q.front();
        q.pop();
        for (int i = 0;i < 4;i++) {
            if (inside(s.first + dx[i], s.second + dy[i])) {
                if (dist[s.first + dx[i]][s.second + dy[i]] == 1e9 && grid[s.first + dx[i]][s.second + dy[i]] != 'T') {
                    q.push({s.first + dx[i], s.second + dy[i]});
                    dist[s.first + dx[i]][s.second + dy[i]] = dist[s.first][s.second] + 1;
                }
            }
        }
    }
    int l = 0;
    int r = 2*n;
    while (l < r) {
        int m = (l+r+1)/2;
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < n;j++) {
                path[i][j] = 1e9;
            }
        }
        queue<pair<int, int>> q;
        q.push(start);
        path[start.first][start.second] = 0;
        while (!q.empty()) {
            pair<int, int> t = q.front();
            q.pop();
            for (int i = 0;i < 4;i++) {
                if (inside(t.first+dx[i], t.second+dy[i])) {
                    if (grid[t.first+dx[i]][t.second+dy[i]] != 'T' && (dist[t.first+dx[i]][t.second+dy[i]]-m) > (path[t.first][t.second] + 1)/s) {
                        if (path[t.first+dx[i]][t.second+dy[i]] > path[t.first][t.second] + 1) {
                            q.push({t.first+dx[i], t.second+dy[i]});
                            path[t.first+dx[i]][t.second+dy[i]] = path[t.first][t.second] + 1;
                        }
                    }
                }
            }
        }
        if (path[home.first][home.second] != 1e9) {
            l = m;
        } else {
            r = m-1;
        }
    }
    if (l == 0 && path[home.first][home.second] == 1e9) {
        cout << -1 << endl;
        return 0;
    }
    cout << l << endl;
}

• Subtask 1: 16 / 100