Submission #1129632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129632		xtl	Mecho (IOI09_mecho)	C++20	20 / 100	77 ms	6216 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
int N, S;
pair<int, int> bearStart;
string graph[800];
int bee[800][800];
int bear[800][800];
bool check(int x)
{
    memset(bear, -1, sizeof(bear));
    deque<pair<int, int>> dq;
    dq.push_back(bearStart);
    bear[bearStart.first][bearStart.second] = x * S;
    while (!dq.empty())
    {
        pair<int, int> v = dq.front();
        dq.pop_front();
        if (v.first >= 1 && bear[v.first - 1][v.second] == -1 && graph[v.first - 1][v.second] != 'T' && bear[v.first][v.second] + 1 < bee[v.first - 1][v.second])
        {
            if (graph[v.first - 1][v.second] == 'D')
                return true;
            bear[v.first - 1][v.second] = bear[v.first][v.second] + 1;
            dq.push_back({v.first - 1, v.second});
        }
        if (v.second >= 1 && bear[v.first][v.second - 1] == -1 && graph[v.first][v.second - 1] != 'T' && bear[v.first][v.second] + 1 < bee[v.first][v.second - 1])
        {
            if (graph[v.first][v.second - 1] == 'D')
                return true;
            bear[v.first][v.second - 1] = bear[v.first][v.second] + 1;
            dq.push_back({v.first, v.second - 1});
        }
        if (v.first < N - 1 && bear[v.first + 1][v.second] == -1 && graph[v.first + 1][v.second] != 'T' && bear[v.first][v.second] + 1 < bee[v.first + 1][v.second])
        {
            if (graph[v.first + 1][v.second] == 'D')
                return true;
            bear[v.first + 1][v.second] = bear[v.first][v.second] + 1;
            dq.push_back({v.first + 1, v.second});
        }
        if (v.second < N - 1 && bear[v.first][v.second + 1] == -1 && graph[v.first][v.second + 1] != 'T' && bear[v.first][v.second] + 1 < bee[v.first][v.second + 1])
        {
            if (graph[v.first][v.second + 1] == 'D')
                return true;
            bear[v.first][v.second + 1] = bear[v.first][v.second] + 1;
            dq.push_back({v.first, v.second + 1});
        }
    }
    return false;
}
int main()
{
    cin.sync_with_stdio(0);
    cin.tie(0);
    memset(bee, -1, sizeof(bee));
    cin >> N >> S;
    for (int r = 0; r < N; r++)
        cin >> graph[r];
    deque<pair<int, int>> dq;
    for (int r = 0; r < N; r++)
        for (int c = 0; c < N; c++)
            if (graph[r][c] == 'H')
            {
                dq.push_back({r, c});
                bee[r][c] = 0;
            }
            else if (graph[r][c] == 'M')
                bearStart = {r, c};
            else if (graph[r][c] == 'D')
                bee[r][c] = 2000000000;
    while (!dq.empty())
    {
        pair<int, int> v = dq.front();
        dq.pop_front();
        if (v.first >= 1 && bee[v.first - 1][v.second] == -1 && graph[v.first - 1][v.second] != 'T' && graph[v.first - 1][v.second] != 'D')
        {
            bee[v.first - 1][v.second] = bee[v.first][v.second] + S;
            dq.push_back({v.first - 1, v.second});
        }
        if (v.second >= 1 && bee[v.first][v.second - 1] == -1 && graph[v.first][v.second - 1] != 'T' && graph[v.first][v.second - 1] != 'D')
        {
            bee[v.first][v.second - 1] = bee[v.first][v.second] + S;
            dq.push_back({v.first, v.second - 1});
        }
        if (v.first < N - 1 && bee[v.first + 1][v.second] == -1 && graph[v.first + 1][v.second] != 'T' && graph[v.first + 1][v.second] != 'D')
        {
            bee[v.first + 1][v.second] = bee[v.first][v.second] + S;
            dq.push_back({v.first + 1, v.second});
        }
        if (v.second < N - 1 && bee[v.first][v.second + 1] == -1 && graph[v.first][v.second + 1] != 'T' && graph[v.first][v.second + 1] != 'D')
        {
            bee[v.first][v.second + 1] = bee[v.first][v.second] + S;
            dq.push_back({v.first, v.second + 1});
        }
    }
    int lo = 0;
    int hi = 20;
    lo--;
    while (lo < hi)
    {
        int mid = lo + (hi - lo + 1) / 2;
        if (check(mid))
            lo = mid;
        else
            hi = mid - 1;
    }
    cout << lo;
}

• Subtask 1: 20 / 100