Submission #1016211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016211		socpite	Mecho (IOI09_mecho)	C++14	100 / 100	121 ms	24920 KiB

mecho

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

const int maxn = 805;
const int INF = 1e9;

const pair<int, int> mv[4] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};

int n, s;
char board[maxn][maxn];

bool inb(int a, int b){
    return a >= 1 && a <= n && b >= 1 && b <= n;
}

bool chk(int a, int b){
    return inb(a, b) && board[a][b] != 'D' && board[a][b] != 'T';
}

int dm[maxn][maxn], db[maxn][maxn]; 
int val[maxn][maxn];
vector<pair<int, int>> pq[maxn*maxn];

bool chk(int dist){
    queue<pair<int, int>> q;
    memset(dm, -1, sizeof(dm));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++)if(board[i][j] == 'M'){
            dm[i][j] = 0;
            q.push({i, j});
        }
    }
    while(!q.empty()){
        auto x = q.front();
        q.pop();
        if(dm[x.first][x.second]/s + dist >= db[x.first][x.second])continue;
        for(auto v: mv){
            int nx = x.first + v.first, ny = x.second + v.second;
            if(inb(nx, ny) && board[nx][ny] == 'D')return true;
            if(dm[nx][ny] == -1 && chk(nx, ny)){
                dm[nx][ny] = dm[x.first][x.second] + 1;
                q.push({nx, ny});
            }
        }
    }
    return false;

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> s;
    queue<pair<int, int>> q;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> board[i][j];
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(board[i][j] == 'H')q.push({i, j});
            else db[i][j] = INF;
        }
    }
    while(!q.empty()){
        auto x = q.front();
        q.pop();
        for(auto v: mv){
            int nx = x.first + v.first, ny = x.second + v.second;
            if(db[nx][ny] == INF && chk(nx, ny)){
                db[nx][ny] = db[x.first][x.second] + 1;
                q.push({nx, ny});
            }
        }
    }
    int l = -1, r = maxn*maxn;
    while(l < r){
        int mid = (l+r+1)>>1;
        if(chk(mid))l = mid;
        else r = mid - 1;
    }
    cout << l;

}

• Subtask 1: 100 / 100