Submission #396875

#	Time	Username	Problem	Language	Result	Execution time	Memory
396875		rocks03	Mecho (IOI09_mecho)	C++14	100 / 100	196 ms	9004 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << " "
#define nl cout << "\n"
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int dx[] = {-1, +1, 0, 0};
int dy[] = {0, 0, -1, +1};

const int MAXN = 1e3+100;
int N, S, sx, sy, ex, ey, d[MAXN][MAXN], D[MAXN][MAXN];
char mat[MAXN][MAXN];

bool valid(int x, int y){
    return (x >= 0 && x < N && y >= 0 && y < N && mat[x][y] != 'T');
}

bool check(int mid){
    if(mid >= d[sx][sy]){
        return false;
    }
    rep(i, 0, N){
        rep(j, 0, N){
            D[i][j] = INT_MAX;
        }
    }
    D[sx][sy] = 0;
    queue<pii> q;
    q.push({sx, sy});
    while(!q.empty()){
        auto [x, y] = q.front();
        q.pop();
        int dist = (D[x][y] + 1) / S;
        rep(i, 0, 4){
            int x2 = x + dx[i], y2 = y + dy[i];
            if(valid(x2, y2) && D[x2][y2] == INT_MAX && d[x2][y2] > dist + mid){
                D[x2][y2] = D[x][y] + 1;
                q.push({x2, y2});
            }
        }
    }
    if(D[ex][ey] != INT_MAX)
        return true;
    return false;
}

void solve(){
    cin >> N >> S;
    queue<pii> q;
    rep(i, 0, N){
        string s; cin >> s;
        rep(j, 0, N){
            char c = mat[i][j] = s[j];
            d[i][j] = INT_MAX;
            if(c == 'H'){
                d[i][j] = 0;
                q.push({i, j});
            }
            if(c == 'M'){
                sx = i, sy = j;
            }
            if(c == 'D'){
                ex = i, ey = j;
            }
        }
    }
    while(!q.empty()){
        auto [x, y] = q.front();
        q.pop();
        rep(i, 0, 4){
            int x2 = x + dx[i], y2 = y + dy[i];
            if(valid(x2, y2) && d[x2][y2] == INT_MAX && mat[x2][y2] != 'D'){
                d[x2][y2] = d[x][y] + 1;
                q.push({x2, y2});
            }
        }
    }
    int l = -1, r = 1e9;
    while(r - l > 1){
        int m = (l + r) / 2;
        if(check(m)) l = m;
        else r = m;
    }
    cout << l;
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    solve();
    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'bool check(int)':
mecho.cpp:41:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |         auto [x, y] = q.front();
      |              ^
mecho.cpp: In function 'void solve()':
mecho.cpp:78:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |         auto [x, y] = q.front();
      |              ^

• Subtask 1: 100 / 100