Submission #970852

#	Time	Username	Problem	Language	Result	Execution time	Memory
970852		Thunnus	Mecho (IOI09_mecho)	C++17	100 / 100	262 ms	3080 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define sz(x) (int)(x).size()
#define pii pair<int,int>
#define fi first
#define se second

const int MAXN = 800;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};
int n, s;
vector<string> forest(MAXN);
queue<array<int, 3>> hives;
pii start;

inline bool inside(int x, int y) {return x >= 0 && x < n && y >= 0 && y < n;}

inline bool check(int time){
    vector<string> t_forest = forest;
    queue<array<int, 3>> bees = hives;
    queue<array<int, 3>> frontier;
    vector<vb> vis(vector<vb>(n, vb(n)));
    int minutes = 0;
    while(!bees.empty()){
        array<int, 3> b = bees.front();
        if(b[2] == time)
            break;
        bees.pop();
        for(int i = 0; i < 4; i++){
            int new_x = b[0] + dx[i];
            int new_y = b[1] + dy[i];
            if(inside(new_x, new_y) && (t_forest[new_x][new_y] == 'G' || t_forest[new_x][new_y] == 'M')){
                bees.push({new_x, new_y, b[2] + 1});
                t_forest[new_x][new_y] = 'H';
            }
        }
        if(t_forest[start.fi][start.se] == 'H')
                return false;
    }

    frontier.push({start.fi, start.se, 0});
    vis[start.fi][start.se] = true;
    while(!frontier.empty()){
        minutes++;
        while(frontier.front()[2] < s * minutes && !frontier.empty()){
            array<int, 3> c = frontier.front();
            frontier.pop();
            if(t_forest[c[0]][c[1]] == 'H') continue;
            for(int j = 0; j < 4; j++){
                int new_x = c[0] + dx[j];
                int new_y = c[1] + dy[j];
                if(inside(new_x, new_y) && (t_forest[new_x][new_y] == 'G' || t_forest[new_x][new_y] == 'D') && !vis[new_x][new_y]){
                    if(t_forest[new_x][new_y] == 'D'){
                        return true;
                    }
                    frontier.push({new_x, new_y, c[2] + 1});
                    vis[new_x][new_y] = true;
                }
            }
        }

        int size = sz(bees);
        while(size--){
            array<int, 3> b = bees.front();
            bees.pop();
            for(int i = 0; i < 4; i++){
                int new_x = b[0] + dx[i];
                int new_y = b[1] + dy[i];
                if(inside(new_x, new_y) && (t_forest[new_x][new_y] == 'G' || t_forest[new_x][new_y] == 'M')){
                    bees.push({new_x, new_y, b[2] + 1});
                    t_forest[new_x][new_y] = 'H';
                }
            }
        }
    }
    return false;
}

int binary_search(){
    int le = 0, ri = n * n;
    while(le <= ri){
        int mid = le + ((ri - le) >> 1);
        if(check(mid)){
            le = mid + 1;
        }
        else{
            ri = mid - 1;
        }
    }
    return le - 1;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> s;
    for(int i = 0; i < n; i++){
        cin >> forest[i];
        for(int j = 0; j < n; j++){
            if(forest[i][j] == 'H')
                hives.push({i, j, 0});
            else if(forest[i][j] == 'M')
                start = {i, j};
        }
    }
    cout << binary_search();
    return 0;
}

• Subtask 1: 100 / 100