Submission #773344

#	Time	Username	Problem	Language	Result	Execution time	Memory
773344		sz1218	Mecho (IOI09_mecho)	C++14	95 / 100	140 ms	6316 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pll;
typedef vector<int> vi;

#define pb push_back
#define f first
#define s second

int __i__, __j__;
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}

#define For(i,a,b) for (int i = (a); i < (b); ++i)
#define Fir(i,a) For(i,0,a)
#define Rof(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define Rif(i,a) Rof(i,0,a)

const int NN = 805, mod = 1e9 + 7, INF = 0x3f3f3f3f;
int n, S, dism[NN][NN], disb[NN][NN], mx, my, ex, ey, dir[4][2]{{0, 1}, {0, -1}, {-1, 0}, {1, 0}}, ans;char g[NN][NN];
queue<pi> qb;

bool check(int x, int y){
    return 1 <= x && x <= n && 1 <= y && y <= n && g[x][y] != 'T';
}

void bfs(){
    while(!qb.empty()){
        auto[ux, uy] = qb.front(); qb.pop();
        For(d, 0, 4){
            int nx = ux + dir[d][0],  ny = uy + dir[d][1];
            if(check(nx, ny)){
                if(disb[nx][ny] == INF){
                    disb[nx][ny] = disb[ux][uy] + 1;
                    qb.push({nx, ny});
                }
            }
        }
    }
}

bool escapable(int delay){
    memset(dism, 0x3f, sizeof(dism));
    queue<pi> q; q.push({mx, my});dism[mx][my] = 0;
    if(delay >= disb[mx][my])return false;
    while(!q.empty()){
        auto[x, y] = q.front(); q.pop();
        For(d, 0, 4){
            int nx = x + dir[d][0], ny = y+dir[d][1];
            if(check(nx, ny)){
                if(dism[nx][ny] == INF){
                    if(nx == ex && ny == ey){
                        return true;
                    }
                    if( (dism[x][y]+1)/S < disb[nx][ny] - delay){
                        dism[nx][ny] = dism[x][y] + 1;
                        q.push({nx, ny});
                    }
                }
            }
        }
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> S;
    memset(disb, 0x3f, sizeof(disb));
    For(i, 1, n+1){
        For(j, 1, n+1){
            cin >> g[i][j];
            if(g[i][j] == 'M'){
                mx = i; my = j;
            }
            if(g[i][j] == 'H'){
                qb.push({i, j}); disb[i][j] = 0;
            }
            if(g[i][j] == 'D'){
                ex = i; ey = j;
            }
        }
    }

    bfs(); disb[ex][ey] = INF;
    int lo = 0, hi = 7e5; ans = -1;
    while(lo <= hi){
        int mid = (lo + hi)/2;
        if(escapable(mid)){
            ans = mid; lo = mid+1;
        }
        else{
            hi = mid-1;
        }
    }

    cout << ans << endl;
    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'void bfs()':
mecho.cpp:34:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |         auto[ux, uy] = qb.front(); qb.pop();
      |             ^
mecho.cpp: In function 'bool escapable(int)':
mecho.cpp:52:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |         auto[x, y] = q.front(); q.pop();
      |             ^

• Subtask 1: 95 / 100