제출 #1021247

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1021247		NguyenPhucThang	Mecho (IOI09_mecho)	C++14	71 / 100	155 ms	12060 KiB

mecho

#include <bits/stdc++.h>
#define forr(i, a, b) for (int i = (a); i <= (b); i++)
#define ford(i, a, b) for (int i = (a); i >= (b); i--)
#define forf(i, a, b) for (int i = (a); i < (b); i++)
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vii vector<pii>
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

using namespace std;
const int base = 31;
const ll mod = 1e9 + 7;
const ll oo = 1e18;
const int N = 805;

char a[N][N];
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

int M[N][N], H[N][N], d[N][N], dd[N][N], xm, ym, xd, yd, n, S;

bool check(int t){
    queue<pii> q;
    forr(i, 1, n) forr(j, 1, n) dd[i][j] = false;
    
    if (H[xm][ym] <= t) return false;
    q.push({xm, ym});   
    dd[xm][ym] = true;

    while (!q.empty()){
        pii u = q.front();
        q.pop();
        forr(i, 0, 3){
            int nx = u.fi + dx[i], ny = u.se + dy[i];
            if (1 <= nx && nx <= n && 1 <= ny && ny <= n && a[nx][ny] != 'T' && !dd[nx][ny]){
                if ((M[u.fi][u.se] + 1) / S + t < H[nx][ny]){
                    dd[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
    }

    forr(i, 0, 3){
        int x = xd + dx[i], y = yd + dy[i];
        if (1 <= x && x <= n && 1 <= y && y <= n && M[x][y]/S + t < H[x][y] && dd[x][y]) return true;
    }
    return false;
}

int main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);

    cin >> n >> S;
    forr(i, 1, n) forr(j, 1, n) {
        cin >> a[i][j];
        if (a[i][j] == 'M') xm = i, ym = j;
        if (a[i][j] == 'D') xd = i, yd = j;
    }
    
    queue<pii> q;
    d[xm][ym] = 1;
    q.push({xm, ym});
    while (!q.empty()){
        pii u = q.front();
        q.pop();
        forr(i, 0, 3){
            int nx = u.fi + dx[i], ny = u.se + dy[i];
            if (1 <= nx && nx <= n && 1 <= ny && ny <= n && a[nx][ny] != 'T' && !d[nx][ny]){
                d[nx][ny] = d[u.fi][u.se] + 1;
                q.push({nx, ny});
            }
        }
    }

    forr(i, 1, n) forr(j, 1, n) M[i][j] = d[i][j] - 1;

    forr(i, 1, n) forr(j, 1, n) if (a[i][j] == 'H') q.push({i, j}), H[i][j] = 1;

    while (!q.empty()){
        pii u = q.front();
        q.pop();
        forr(i, 0, 3){
            int nx = u.fi + dx[i], ny = u.se + dy[i];
            if (1 <= nx && nx <= n && 1 <= ny && ny <= n && a[nx][ny] != 'T' && !H[nx][ny]){
                H[nx][ny] = H[u.fi][u.se] + 1;
                q.push({nx, ny});
            }
        }
    }

    forr(i, 1, n) forr(j, 1, n) if (H[i][j]) H[i][j]--;

    int l = 0, r = n*n, ans = -1;
    while (l <= r){
        int mid = (l + r) >> 1;
        if (check(mid)){
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    
    cout << ans << endl;
  
   return 0;
}

• Subtask 1: 71 / 100