Submission #1134824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134824		duonggsimp	Mecho (IOI09_mecho)	C++20	13 / 100	146 ms	15968 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll,ll> ii;
typedef pair <ii,ii> iii;
#define pb push_back
#define fi first
#define se second
#define endl '\n'
#define N 1000005
#define M 1005
#define MOD 1000000007
const ll dx[] = {0,0,-1,1};
const ll dy[] = {-1,1,0,0};

ll n,s;
ii u,v;
ll d[M][M];
ll dist[M][M];
bool f[M][M];
bool c[M][M];
char a[M][M];
queue <ii> q1;
queue <ii> q;

void debug(){
    for (long i=1; i<=n; i++){
        for (long j=1; j<=n; j++) cerr << dist[i][j] << ' ';
        cerr << endl;
    }
}

bool check(ll x,ll y){
    return (dist[x][y] / s) < d[x][y];
}

void setup(){

    for (long i=1; i<=n; i++){
        for (long j=1; j<=n; j++){
            if (a[i][j] != 'H') d[i][j] = 1e18;
        }
    }

    while (!q1.empty()){
        ii t = q1.front(); q1.pop();

        for (long i=0; i<4; i++){
            ll x = t.fi + dx[i];
            ll y = t.se + dy[i];
            if (x >= 1 && y >= 1 && x <= n && y <= n && !f[x][y]){
                f[x][y] = 1;
                d[x][y] = min(d[x][y],d[t.fi][t.se] + 1);
                q1.push({x,y});
            }
        }
    }
}

bool bfs(ll mid){

    for (long i=1; i<=n; i++){
        for (long j=1; j<=n; j++){
            c[i][j] = 0;
            dist[i][j] = 0;
        }
    }

    c[u.fi][u.se] = 1;
    dist[u.fi][u.se] = mid + 1;
    q.push({u.fi,u.se});

    while (!q.empty()){

        ii t2 = q.front();
        q.pop();

        for (long i=0; i<4; i++){
            ll x = t2.fi + dx[i];
            ll y = t2.se + dy[i];
            if (x >= 1 && y >= 1 && x <= n && y <= n && !c[x][y] && a[x][y] != 'T' && check(t2.fi,t2.se)){
                c[x][y] = 1;
                dist[x][y] = dist[t2.fi][t2.se] + 1;
                q.push({x,y});

            }
        }
    }

    return c[v.fi][v.se];
}

signed main(){

//    #ifndef ONLINE_JUDGE
//    freopen("test.inp", "r", stdin);
//    freopen("test.out" ,"w", stdout);
//    #endif

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> s;

    for (long i=1; i<=n; i++){
        for (long j=1; j<=n; j++){
            cin >> a[i][j];
            if (a[i][j] == 'M'){
                u.fi = i;
                u.se = j;
            }
            if (a[i][j] == 'D'){
                v.fi = i;
                v.se = j;
            }
            if (a[i][j] == 'H'){
                 q1.push({i,j});
                 d[i][j] = 0;
                 f[i][j] = 1;
            }
        }
    }

    setup();

//    for (long i=1; i<=n; i++){
//        for (long j=1; j<=n; j++) cout << d[i][j] << ' ';
//        cout << endl;
//    }

    ll l = 1, r = 1e3;
    while (l <= r){
        ll mid = l + r >> 1;
        if (bfs(mid)){
            l = mid + 1;
        } else r = mid - 1;
//        debug();
//        cerr << endl;
    }

    cout << l / s;
    return 0;
}

• Subtask 1: 13 / 100