Submission #483953

#	Time	Username	Problem	Language	Result	Execution time	Memory
483953		nehasane	Mecho (IOI09_mecho)	C++14	10 / 100	1094 ms	5828 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 800;
vector <string> field(MAX_N);
bool bees_visited[MAX_N][MAX_N], mecho_visited[MAX_N][MAX_N];
int dis[MAX_N][MAX_N];
queue <pair <int, int>> mecho_q, bees_q;
int n, s;
bool valid_sq(int x, int y, bool mecho){
    if (x >= 0 && x < n && y >= 0 && y < n){
        if (mecho && (field[x][y] == 'G' || field[x][y] == 'D' || field[x][y] == 'M'))
            return true;
        else if (!mecho && (field[x][y] == 'G' || field[x][y] == 'H'))
            return true;
        return false;
    }
    return false;
}
void move_bees(int x, int y, bool add){
    if (valid_sq(x-1, y, false) && !bees_visited[x-1][y]){
        if (add)
            bees_q.push({x-1, y});
        bees_visited[x-1][y] = true;
    }
    if (valid_sq(x+1, y, false) && !bees_visited[x+1][y]){
        if (add)
            bees_q.push({x+1, y});
        bees_visited[x+1][y] = true;
    }
    if (valid_sq(x, y-1, false) && !bees_visited[x][y-1]){
        if (add)
            bees_q.push({x, y-1});
        bees_visited[x][y-1] = true;
    }
    if (valid_sq(x, y+1, false) && !bees_visited[x][y+1]){
        if (add)
            bees_q.push({x, y+1});
        bees_visited[x][y+1] = true;
    }
}
void move_mecho(int x, int y, bool add){
    if (valid_sq(x-1, y, true) && !mecho_visited[x-1][y] && !bees_visited[x-1][y]){
        mecho_visited[x-1][y] = true;
        if (add)
            mecho_q.push({x-1, y});
    }
    if (valid_sq(x+1, y, true) && !mecho_visited[x+1][y] && !bees_visited[x+1][y]){
        mecho_visited[x+1][y] = true;
        if (add)
            mecho_q.push({x+1, y});
    }
    if (valid_sq(x, y-1, true) && !mecho_visited[x][y-1] && !bees_visited[x][y-1]){
        mecho_visited[x][y-1] = true;
        if (add)
            mecho_q.push({x, y-1});
    }
    if (valid_sq(x, y+1, true) && !mecho_visited[x][y+1] && !bees_visited[x][y+1]){
        mecho_visited[x][y+1] = true;
        if (add)
            mecho_q.push({x, y+1});
    }
}
void mecho_bfs(){
    while (!mecho_q.empty() && dis[mecho_q.front().first][mecho_q.front().second] < s){
        int x = mecho_q.front().first, y = mecho_q.front().second;
        mecho_q.pop();
        if (dis[x][y] >= s){
            mecho_q.push({x, y});
            continue;
        }
        if (valid_sq(x-1, y, true) && !mecho_visited[x-1][y] && !bees_visited[x-1][y] && dis[x][y] + 1 <= s){
            mecho_visited[x-1][y] = true;
            mecho_q.push({x-1, y});
            dis[x-1][y] = dis[x][y] + 1;
        }
        if (valid_sq(x+1, y, true) && !mecho_visited[x+1][y] && !bees_visited[x+1][y] && dis[x][y] + 1 <= s){
            mecho_visited[x+1][y] = true;
            mecho_q.push({x+1, y});
            dis[x+1][y] = dis[x][y] + 1;
        }
        if (valid_sq(x, y-1, true) && !mecho_visited[x][y-1] && !bees_visited[x][y-1] && dis[x][y] + 1 <= s){
            mecho_visited[x][y-1] = true;
            mecho_q.push({x, y-1});
            dis[x][y-1] = dis[x][y] + 1;
        }
        if (valid_sq(x, y+1, true) && !mecho_visited[x][y+1] && !bees_visited[x][y+1] && dis[x][y] + 1 <= s){
            mecho_visited[x][y+1] = true;
            mecho_q.push({x, y+1});
            dis[x][y+1] = dis[x][y] + 1;
        }
    }
}
int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    cin >> n >> s;
    for (int i = 0; i < n; i++)
        cin >> field[i];
    vector <pair <int, int>> hives;
    int startx, starty, home_x, home_y;
    //find Mecho's position
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            if (field[i][j] == 'M'){
                startx = i;
                starty = j;
            }else if (field[i][j] == 'H'){
                hives.push_back({i, j});
            }else if (field[i][j] == 'D'){
                home_x = i;
                home_y = j;
            }
        }
    }
    int l = 0, r = n + n - 2;
    while (l <= r){
        int eating_time = (l + r) / 2;
        memset(bees_visited, false, sizeof(bees_visited));
        memset(mecho_visited, false, sizeof(mecho_visited));
        //simulate
        //move only bees, since mecho is eating
        for (auto i : hives){
            bees_q.push({i.first, i.second});
            bees_visited[i.first][i.second] = true;
        }

        for (int i = 0; i < eating_time; i++){
            int si = bees_q.size();
            for (int j = 0; j < si; j++){
                move_bees(bees_q.front().first, bees_q.front().second, true);
                bees_q.pop();
            }
        }    
        //move mecho and bees
        mecho_q.push({startx, starty});
        for (int i = eating_time; i < 2 * n - 2; i++){            
            mecho_bfs();
            memset(dis, 0, sizeof(dis));
            int si = bees_q.size();
            for (int j = 0; j < si; j++){
                move_bees(bees_q.front().first, bees_q.front().second, true);
                bees_q.pop();
            }
        }
        if (mecho_visited[home_x][home_y])
            l = eating_time + 1;
        else
            r = eating_time - 1;
        //empty both queues
        while (!bees_q.empty())
            bees_q.pop();
        while (!mecho_q.empty())
            mecho_q.pop();
    }
    cout << r << '\n';
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:146:41: warning: 'home_y' may be used uninitialized in this function [-Wmaybe-uninitialized]
  146 |         if (mecho_visited[home_x][home_y])
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
mecho.cpp:146:41: warning: 'home_x' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 10 / 100