Submission #566142

#	Time	Username	Problem	Language	Result	Execution time	Memory
566142		faruk	Mecho (IOI09_mecho)	C++17	63 / 100	259 ms	2632 KiB

mecho

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ll long long
#define ld long double

using namespace std;

vector<string> grid;
int n, s;

void expand(queue<pii>& bees, vector<string>& mat, vector<vector<bool> > &expanded ) {

    queue<pii> newque;
    while (!bees.empty()) {
        pii curr = bees.front();
        bees.pop();

        if (expanded[curr.first][curr.second])
            continue;
        
        if (mat[curr.first + 1][curr.second] == 'G' || mat[curr.first + 1][curr.second] == 'M')
            mat[curr.first + 1][curr.second] = 'H', newque.push({curr.first + 1, curr.second});
        if (mat[curr.first - 1][curr.second] == 'G' || mat[curr.first - 1][curr.second] == 'M')
            mat[curr.first - 1][curr.second] = 'H', newque.push({curr.first - 1, curr.second});
        if (mat[curr.first][curr.second + 1] == 'G' || mat[curr.first][curr.second + 1] == 'M')
            mat[curr.first][curr.second + 1] = 'H', newque.push({curr.first, curr.second + 1});
        if (mat[curr.first][curr.second - 1] == 'G' || mat[curr.first][curr.second - 1] == 'M')
            mat[curr.first][curr.second - 1] = 'H', newque.push({curr.first, curr.second - 1});
        expanded[curr.first][curr.second] = true;
    }

    bees = newque;
}

bool possible(int wait, queue<pii> bees, pii start, pii endd) {
    vector<vector<bool> > expanded(n + 2, vector<bool>(n + 2, false));
    vector<string> mat = grid;
    mat[start.first][start.second] = 'G';


    for (int i = 0; i < wait; i++)
        expand(bees, mat, expanded);

    vector<vector<bool> > visited(n + 2, vector<bool>(n + 2, false));
    int tim = s;
    queue<pair<int, pii> > que;

    que.push({0, {start.first, start.second}});
    while (!que.empty())
    {
        pair<int, pii> curr = que.front();
        que.pop();

        if (curr.first == tim) {
            expand(bees, mat, expanded);
            tim += s;
        }

        if (!(mat[curr.second.first][curr.second.second] == 'G' || mat[curr.second.first][curr.second.second] == 'D')
         || visited[curr.second.first][curr.second.second])
            continue;
        visited[curr.second.first][curr.second.second] = true;

        que.push({curr.first + 1, {curr.second.first + 1, curr.second.second}});
        que.push({curr.first + 1, {curr.second.first - 1, curr.second.second}});
        que.push({curr.first + 1, {curr.second.first, curr.second.second + 1}});
        que.push({curr.first + 1, {curr.second.first, curr.second.second - 1}});
    }
    
    return visited[endd.first][endd.second];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> s;
    grid.resize(n + 2);
    string wall;
    for (int i = 0; i < n + 2; i++)
        wall += 'T';
    grid[0] = wall, grid[n + 1] = wall;
    for (int i = 1; i <= n; i++) {
        string curr = "T";
        string inp;
        cin >> inp;
        curr += inp;
        curr += 'T';
        grid[i] = curr;
    }

    queue<pii> bees;
    pii start, endd;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (grid[i][j] == 'D')
                endd = {i, j};
            else if (grid[i][j] == 'H')
                bees.push({i, j});
            else if (grid[i][j] == 'M')
                start = {i, j};
        }
    }
    
    int l = 0, r = 10 * n;
    while (l < r) {
        int mid = (l + r) / 2;
        if (possible(mid, bees, start, endd))
            l = 1 + mid;
        else
            r = mid;
    }

    cout << l - 1 << "\n";
}

• Subtask 1: 63 / 100