Submission #104007

#	Time	Username	Problem	Language	Result	Execution time	Memory
104007		Badral	Mecho (IOI09_mecho)	C++17	100 / 100	319 ms	7900 KiB

mecho

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

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

bool asdasd = 0;

bool can(int k) {

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

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

    bear[xx][yy] = 0;

    queue < pi > q;
    
    q.push(make_pair(xx, yy));
        int x, y;    
    while(!q.empty()) {
        tie(x, y) = q.front();
        q.pop();
        for(int i = 1; i <= 4; i++) {
            int 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(int i = 1; i <= n; i++) {
        for(int 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()) {
        int x, y; tie(x, y) = p.front(); p.pop();
        for ( int i = 1; i <= 4; i++ ) {
            int 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 ) );
            }
        }
    }

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

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:68:10: warning: unused variable 'pppp' [-Wunused-variable]
     bool pppp = can(0);
          ^~~~

• Subtask 1: 100 / 100