Submission #1200994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200994		apelpisia	Mecho (IOI09_mecho)	C++20	95 / 100	576 ms	3288 KiB

mecho

#include <bits/stdc++.h>
#define ff first
#define ss second
#define int long long

using namespace std;

const int nx = 805;
int n, s, l=0, r=INT_MAX, md, ans=0;
string grid[nx];
pair<int, int> bear, dir[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
set<pair<int, int>> bee;

bool check(int sz, int steps){
    vector<vector<bool>> b(sz, vector<bool>(sz, false)), br(sz, vector<bool>(sz, false));
    queue<pair<int, pair<int, int>>> bq, brq;
    for(auto [y, x] : bee) bq.push({0, {y, x}});
    brq.push({0, {bear.ff, bear.ss}});
    int bt = md, brt = steps;
    while(!brq.empty()){
        // cout << "!EMPTY\n";
        while(!bq.empty() && bq.front().ff<bt){
            // cout << "LOOP1\n";
            int mins = bq.front().ff;
            pair<int, int> pos = bq.front().ss;
            bq.pop();
            if(b[pos.ff][pos.ss]) continue;
            b[pos.ff][pos.ss] = true;
            for(int i=0; i<4; i++){
                int ny = pos.ff+dir[i].ff, nx = pos.ss+dir[i].ss;
                if(ny>=0 && ny<n && nx>=0 && nx<n && grid[ny][nx]!='T' && !b[ny][nx]){
                    bq.push({mins+1, {ny, nx}});
                }
            }
        } bt++;
        while(!brq.empty() && brq.front().ff<brt){
            // cout << "LOOP2\n";
            int mins = brq.front().ff;
            pair<int, int> pos = brq.front().ss;
            brq.pop();
            if(br[pos.ff][pos.ss] || b[pos.ff][pos.ss]) continue;
            br[pos.ff][pos.ss] = true;
            for(int i=0; i<4; i++){
                int ny = pos.ff+dir[i].ff, nx = pos.ss+dir[i].ss;
                if(ny>=0 && ny<n && nx>=0 && nx<n && grid[ny][nx]!='T' && !br[ny][nx]){
                    if(grid[ny][nx]=='D') return true;
                    brq.push({mins+1, {ny, nx}});
                }
            }
        } brt+=steps;
    }
    return false;
}

signed main(){
    // cin.tie(NULL)->sync_with_stdio(false);
    bool cando = false;
    cin >> n >> s;
    for(int i=0; i<n; i++){
        cin >> grid[i];
        for(int j=0; j<n; j++){
            if(grid[i][j]=='H') bee.insert({i, j});
            else if(grid[i][j]=='M') bear = {i, j};
        }
    }
    while(l<=r){
        md = l+(r-l)/2;
        if(check(n, s)){
            cando = true;
            ans = md;
            l = md+1;
        } else r = md-1;
    }
    if(cando) cout << ans-1;
    else cout << -1;

    return 0;
}

• Subtask 1: 95 / 100