Submission #228799

#	Time	Username	Problem	Language	Result	Execution time	Memory
228799		osaaateiasavtnl	Mecho (IOI09_mecho)	C++14	73 / 100	236 ms	17804 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 1007, INF = 1e9 + 7;
int n, S;
string a[N];
int bee_dist[N][N];
bool can_bee(int i, int j) {
    return 0 <= i && i < n && 0 <= j && j < n && (a[i][j] == 'G' || a[i][j] == 'M' || a[i][j] == 'H');
}   
vector <ii> v = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} };
void bfs1() {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {   
            bee_dist[i][j] = INF;
        }
    }
    queue <ii> q;   
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (a[i][j] == 'H') {
                bee_dist[i][j] = 0;
                q.push(mp(i, j));
            }   
        }   
    }   
    while (q.size()) {
        auto p = q.front(); q.pop();
        for (auto e : v) {
            int x = p.f + e.f, y = p.s + e.s;
            if (can_bee(x, y) && bee_dist[p.f][p.s] + 1 < bee_dist[x][y]) {
                bee_dist[x][y] = bee_dist[p.f][p.s] + 1;
                q.push(mp(x, y));
            }   
        }   
    }   
}   
bool can_bear(int i, int j, int t, int m) {
    t = t / S;
    return 0 <= i && i < n && 0 <= j && j < n && (a[i][j] == 'G' || a[i][j] == 'M' || a[i][j] == 'D') && bee_dist[i][j] > t + m;
}   
int sx, sy;
int dist[N][N];
bool can(int m) {
    if (bee_dist[sx][sy] <= m)  
        return 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            dist[i][j] = INF;
        }   
    }   
    queue <ii> q;
    dist[sx][sy] = 0;
    q.push(mp(sx, sy));
    while (q.size()) {
        auto p = q.front(); q.pop();

        //cout << "point " << p.f << ' ' << p.s << endl;

        if (a[p.f][p.s] == 'D')
            return 1;
        for (auto e : v) {
            int x = p.f + e.f, y = p.s + e.s;
            if (can_bear(x, y, dist[p.f][p.s] + 1, m) && dist[p.f][p.s] + 1 < dist[x][y]) {
                dist[x][y] = dist[p.f][p.s] + 1;
                q.push(mp(x, y));
            }   
        }   
    }   
    return 0;
}   
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> S;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (a[i][j] == 'M') {
                sx = i;
                sy = j;
            }   
        }   
    }
    bfs1();
    #ifdef HOME
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << bee_dist[i][j] << ' ';
        }   
        cout << endl;
    }   
    #endif

    int l = -1, r = 2 * N;
    while (l < r - 1) {
        int m = (l + r) >> 1;
        if (can(m))
            l = m;
        else
            r = m;
    }   
    cout << l << endl;
}

• Subtask 1: 73 / 100