Submission #286241

#	Time	Username	Problem	Language	Result	Execution time	Memory
286241		AaronNaidu	Mecho (IOI09_mecho)	C++14	100 / 100	218 ms	6960 KiB

mecho

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

char board[801][801];
int beeDist[801][801];
int mechoDist[801][801];
int n, s;
pair<int, int> home, mecho;
vector<pair<int, int> > hives;

bool canEscapeAfter(int a) {
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            mechoDist[i][j] = -1;    
        }
    }
    queue<pair<int, int> > q;
    q.push(mecho);
    mechoDist[mecho.first][mecho.second] = s * a;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        if (x == home.first and y == home.second)
        {
            return true;
        }
        if (mechoDist[x][y]/s >= beeDist[x][y])
        {
            continue;
        }
        if (0 <= x+1 and x+1 < n)
        {
            if (board[x+1][y] == 'G' or board[x+1][y] == 'D')
            {
                if (mechoDist[x+1][y] == -1)
                {
                    mechoDist[x+1][y] = mechoDist[x][y] + 1;
                    q.push({x+1, y});
                }
            }
        }
        if (0 <= x-1 and x-1 < n)
        {
            if (board[x-1][y] == 'G' or board[x-1][y] == 'D')
            {
                if (mechoDist[x-1][y] == -1)
                {
                    mechoDist[x-1][y] = mechoDist[x][y] + 1;
                    q.push({x-1, y});
                }
            }
        }
        if (0 <= y+1 and y+1 < n)
        {
            if (board[x][y+1] == 'G' or board[x][y+1] == 'D')
            {
                if (mechoDist[x][y+1] == -1)
                {
                    mechoDist[x][y+1] = mechoDist[x][y] + 1;
                    q.push({x, y+1});
                }
            }
        }
        if (0 <= y-1 and y-1 < n)
        {
            if (board[x][y-1] == 'G' or board[x][y-1] == 'D')
            {
                if (mechoDist[x][y-1] == -1)
                {
                    mechoDist[x][y-1] = mechoDist[x][y] + 1;
                    q.push({x, y-1});
                }
            }
        }
    } 
    return false;
}

int main() {
    cin >> n >> s;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> board[i][j];
            beeDist[i][j] = -1;
            if (board[i][j] == 'H')
            {
                hives.push_back({i,j});
            }
            if (board[i][j] == 'M')
            {
                mecho = {i,j};
            }
            if (board[i][j] == 'D')
            {
                home = {i,j};
            }
        }
    }
    queue<pair<int, int> > bees;
    for (auto i : hives)
    {
        bees.push(i);
        beeDist[i.first][i.second] = 0;
    }
    while (!bees.empty())
    {
        int x = bees.front().first;
        int y = bees.front().second;
        bees.pop();
        if (0 <= x+1 and x+1 < n)
        {
            if (board[x+1][y] == 'G' or board[x+1][y] == 'M')
            {
                if (beeDist[x+1][y] == -1)
                {
                    beeDist[x+1][y] = beeDist[x][y] + 1;
                    bees.push({x+1, y});
                }
            }
        }
        if (0 <= x-1 and x-1 < n)
        {
            if (board[x-1][y] == 'G' or board[x-1][y] == 'M')
            {
                if (beeDist[x-1][y] == -1)
                {
                    beeDist[x-1][y] = beeDist[x][y] + 1;
                    bees.push({x-1, y});
                }
            }
        }
        if (0 <= y+1 and y+1 < n)
        {
            if (board[x][y+1] == 'G' or board[x][y+1] == 'M')
            {
                if (beeDist[x][y+1] == -1)
                {
                    beeDist[x][y+1] = beeDist[x][y] + 1;
                    bees.push({x, y+1});
                }
            }
        }
        if (0 <= y-1 and y-1 < n)
        {
            if (board[x][y-1] == 'G' or board[x][y-1] == 'M')
            {
                if (beeDist[x][y-1] == -1)
                {
                    beeDist[x][y-1] = beeDist[x][y] + 1;
                    bees.push({x, y-1});
                }
            }
        }
    }
    int regionStart = 0;
    int regionEnd = beeDist[mecho.first][mecho.second] - 1;
    //cout << "End on " << regionEnd << "\n";
    int ans = -1;
    while (regionStart <= regionEnd)
    {
        int med = (regionStart + regionEnd)/2;
       // cout << "Checking " << med << "\n";
        if (canEscapeAfter(med))
        {
            ans = med;
            regionStart = med + 1;
          //  cout << "Works\n";
        }
        else
        {
            regionEnd = med - 1;
           // cout << "Does'nt work\n";
        }
    }
    cout << ans << "\n";
}

• Subtask 1: 100 / 100