제출 #597578

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
597578		BhavayGoyal	Mecho (IOI09_mecho)	C++14	37 / 100	186 ms	8136 KiB

mecho

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

#define ll long long
#define ld long double
#define ar array
#define vi vector<int>
#define vii vector<vector<int>>
#define pii pair<int, int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define endl "\n"

const int MOD = 1e9+7;
const int inf = 1e9;
const ll linf = 1e18;

// -------------------------------------------------- Main Code --------------------------------------------------

const int N = 800;
int n, s;
int arr[N][N], beesDis[N][N], bearDis[N][N];
queue<pii> bees;
pii st, en;

int di[4] = {0, 0, 1, -1}, dj[4] = {1, -1, 0, 0};

bool isVal(int i, int j) {
    return (i >= 0 && j >= 0 && i < n && j < n && arr[i][j]);
}

void fillBees() {
    while (!bees.empty()) {
        auto f = bees.front(); bees.pop();
        for (int i = 0; i < 4; i++) {
            int ni = f.f+di[i], nj = f.s+dj[i];
            if (isVal(ni, nj) && beesDis[ni][nj] == -1) {
                beesDis[ni][nj] = beesDis[f.f][f.s]+1;
                bees.push({ni, nj});
            }
        }
    }
}

bool isPoss(int i, int j, int dis, int initTime) {
    return ((dis/s)+initTime < beesDis[i][j]);
}

bool isFiss(int initTime) {
    if (beesDis[st.f][st.s] <= initTime) return false;
    memset(bearDis, -1, sizeof bearDis);
    queue<pii> bear; bear.push({st.f, st.s});
    bearDis[st.f][st.s] = 0;
    while (!bear.empty()) {
        auto f = bear.front(); bear.pop();
        for (int i = 0; i < 4; i++) {
            int ni = f.f+di[i], nj = f.s+dj[i];
            if (isVal(ni, nj) && bearDis[ni][nj] == -1 && isPoss(ni, nj, bearDis[f.f][f.s]+1, initTime)) {
                bearDis[ni][nj] = bearDis[f.f][f.s]+1;
                bear.push({ni, nj});
            }
        }
    }

    for (int i = 0; i < 4; i++) {
        int ni = en.f+di[i], nj = en.s+dj[i];
        if (isVal(ni, nj) && bearDis[ni][nj] != -1) return true;
    }

    return false;
}

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

    cin >> n >> s;
    memset(beesDis, -1, sizeof beesDis);
    memset(arr, 0, sizeof arr);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            char x; cin >> x;
            if (x == 'M') st = {i, j};
            if (x == 'D') en = {i, j};
            if (x == 'H') {
                bees.push({i, j});
                beesDis[i][j] = 0;
            }
            if (x == 'G' || x == 'M') arr[i][j] = 1;
        }
    }

    fillBees();

    int i = 0, j = n, ans = inf;
    while (i <= j) {
        int mid = (i+j)/2;
        if (isFiss(mid)) ans = mid, i = mid+1;
        else j = mid-1;
    }
    cout << ans << endl;
}

• Subtask 1: 37 / 100