Submission #1134851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134851		duonggsimp	Mecho (IOI09_mecho)	C++20	58 / 100	143 ms	15944 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,ll s,ll t,ll mid){
    return ((dist[x][y] + 1) / s + mid) < d[s][t];
}

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] && d[x][y] > d[t.fi][t.se] + 1 && a[x][y] != 'T' && a[x][y] != 'D'){
                f[x][y] = 1;
                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] = 1e18;
        }
    }

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

    if (mid >= d[u.fi][u.se]) return 0;

    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 && dist[x][y] > dist[t2.fi][t2.se] + 1 && !c[x][y] && a[x][y] != 'T' && check(t2.fi,t2.se,x,y,mid)){
                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(){

    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();

    ll l = 0, r = 800*800;
    ll res = -1;
    while (l <= r){
        ll mid = l + r >> 1;
        if (bfs(mid)){
            l = mid + 1;
            res = mid;
        } else r = mid - 1;
    }

    cout << res;
    return 0;
}

• Subtask 1: 58 / 100