Submission #103999

#	Time	Username	Problem	Language	Result	Execution time	Memory
103999		Badral	Mecho (IOI09_mecho)	C++17	40 / 100	348 ms	14536 KiB

mecho

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define pi pair<ll, ll>

char a[1015][1015];
ll dx[] = {0, 0, 0, 1, -1, -1, 1, 1, -1};
ll dy[] = {0, 1, -1, 0, 0, -1, -1, 1, 1};
ll bear[1105][1015], bee[1105][1015], xx = -1, yy = -1, xxx = -1, yyy = -1, n, kk;

bool asdasd = 0;

bool can(ll k) {

    if ( k >= bee[xx][yy] ) return 0;

    for ( ll i = 1; i <= n; i++ ) 
        for ( ll j = 1; j <= n; j++ ) 
            bear[i][j] = INT_MAX;

    bear[xx][yy] = 0;

    queue < pi > q;
    
    q.push(make_pair(xx, yy));
        ll x, y;    
    while(!q.empty()) {
        tie(x, y) = q.front();
        q.pop();
        for(ll i = 1; i <= 4; i++) {
            ll x1 = x + dx[i], y1 = y + dy[i];
            if ( a[x1][y1] == 'D' ) {asdasd = 1; return 1;}
            if ( a[x1][y1] == 'G' && bear[x][y] + 1 <= kk * ( bee[x1][y1] - k ) && bear[x1][y1] == INT_MAX ) {
                bear[x1][y1] = bear[x][y] + 1;
                q.push ( make_pair ( x1, y1 ) ); 
            }
        }
    }
    return 0;  
}

int main() {
    cin >> n >> kk;
    queue < pi > p;
    for(ll i = 1; i <= n; i++) {
        for(ll j = 1; j <= n; j++) {
            bee[i][j] = INT_MAX; 
            cin >>a[i][j];
            if ( a[i][j] == 'H' ) {p.push(make_pair(i, j)); bee[i][j] = 0;}
            if ( a[i][j] == 'M' ) xx = i, yy = j;
        }
    }

    while(!p.empty()) {
        ll x, y; tie(x, y) = p.front(); p.pop();
        for ( ll i = 1; i <= 4; i++ ) {
            ll x1 = x + dx[i], y1 = y + dy[i];

            if ( bee[x1][y1] == INT_MAX && ( a[x1][y1] == 'G' || a[x1][y1] == 'M' ) ) {
                bee[x1][y1] = bee[x][y] + 1; p.push ( make_pair ( x1, y1 ) );
            }
        }
    }

    ll k = 0, mm = n * n;
    for(ll i = mm/2; i >= 1; i /= 2) 
        while(i + k <= mm && can(i+k)) 
            k += i;
    if ( !asdasd ) cout << -1;
    else cout << k;

}

• Subtask 1: 40 / 100