Submission #1134818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134818		duonggsimp	Mecho (IOI09_mecho)	C++20	0 / 100	2 ms	328 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 <iii> 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){
    return (abs(x-s) + abs(y-t) <= s);
}

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;
        }
    }

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

    while (!q.empty()){

        ii t1 = q.front().fi;
        ii t2 = q.front().se;
        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'){
                c[x][y] = 1;
                ii cur = {0,0};

                if (check(t1.fi,t1.se,x,y)){
                    dist[x][y] = dist[t1.fi][t1.se];
                    cur = t1;
                } else {
                    dist[x][y] = dist[t1.fi][t1.se] + 1;
                    cnt = 0;
                    cur = {x,y};
                }

                if (dist[x][y] < d[x][y]){
                    q.push({cur,{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();

    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;
    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:109:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |     freopen("test.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:110:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |     freopen("test.out" ,"w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100