Submission #961890

#	Time	Username	Problem	Language	Result	Execution time	Memory
961890		Ariadna	Mecho (IOI09_mecho)	C++14	84 / 100	138 ms	6816 KiB

mecho

#include <bits/stdc++.h>
#define pb push_back

using namespace std;

const int INF = 1e6;

vector<vector<int>> time_bees;

void bfs_bees(vector<pair<int, int>>& hives, int n, vector<vector<char>>& map) {
    queue<pair<int, int>> q;
    for (pair<int, int> h : hives) {
        q.push(h);
        time_bees[h.first][h.second] = 0;
    }

    while (!q.empty()) {
        pair<int, int> pos = q.front();
        q.pop();
        int i = pos.first, j = pos.second;

        if (i > 0 && time_bees[i-1][j] == INF && map[i-1][j] == 'G') {
            time_bees[i-1][j] = time_bees[i][j]+1;
            q.push({i-1, j});
        }
        if (i < n-1 && time_bees[i+1][j] == INF && map[i+1][j] == 'G') {
            time_bees[i+1][j] = time_bees[i][j]+1;
            q.push({i+1, j});
        }
        if (j > 0 && time_bees[i][j-1] == INF && map[i][j-1] == 'G') {
            time_bees[i][j-1] = time_bees[i][j]+1;
            q.push({i, j-1});
        }
        if (j < n-1 && time_bees[i][j+1] == INF && map[i][j+1] == 'G') {
            time_bees[i][j+1] = time_bees[i][j]+1;
            q.push({i, j+1});
        }
    }
}

bool CanGetHome(pair<int, int> r, vector<vector<char>>& map, int s, int t, pair<int, int> d) {
    int n = (int)map.size();
    queue<pair<pair<int, int>, int>> q;
    vector<vector<int>> visited(n, vector<int>(n, 0));
    visited[r.first][r.second] = 1;
    q.push({r, s*t});
    while (!q.empty()) {
        pair<int, int> pos = q.front().first;
        int steps = q.front().second;
        q.pop();
        int i = pos.first, j = pos.second;

        if (pos == d) return true;
        if (pos != r) {
            if (steps%s == 0) {
                if ((steps+s-1)/s >= time_bees[i][j]) continue;
            } else if ((steps+s-1)/s > time_bees[i][j]) continue;
        }
        if (i > 0 && !visited[i-1][j] && map[i-1][j] == 'G') {
            visited[i-1][j] = 1;
            q.push({{i-1, j}, steps+1});
        }  
        if (i < n-1 && !visited[i+1][j] && map[i+1][j] == 'G') {
            visited[i+1][j] = 1;
            q.push({{i+1, j}, steps+1});
        } 
        if (j > 0 && !visited[i][j-1] && map[i][j-1] == 'G') {
            visited[i][j-1] = 1;
            q.push({{i, j-1}, steps+1});
        }
        if (j < n-1 && !visited[i][j+1] && map[i][j+1] == 'G') {
            visited[i][j+1] = 1;
            q.push({{i, j+1}, steps+1});
        }
    }
    return false;
}

int main() {
    int n, s;
    cin >> n >> s;
    vector<vector<char>> map(n, vector<char>(n));
    vector<pair<int, int>> hives;
    pair<int, int> mecho, home;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> map[i][j];
            if (map[i][j] == 'H') hives.pb({i, j});
            else if (map[i][j] == 'M') { 
                mecho = {i, j};
                map[i][j] = 'G';
            } else if (map[i][j] == 'D') home = {i, j};
        }
    }

    time_bees = vector<vector<int>>(n, vector<int>(n, INF));
    map[home.first][home.second] = 'G';
    bfs_bees(hives, n, map);

    int l = 0, r = time_bees[home.first][home.second]+1, ans = -1;
    while (l <= r) {
        int m = (l+r)/2;
        if (CanGetHome(mecho, map, s, m, home)) {
            l = m+1;
            ans = m;
        } else r = m-1;
    }
    cout << ans << '\n';

    return 0;
}

• Subtask 1: 84 / 100