Submission #484408

#	Time	Username	Problem	Language	Result	Execution time	Memory
484408		Dirii	Mecho (IOI09_mecho)	C++14	15 / 100	1089 ms	65540 KiB

mecho

// #pragma GCC target("avx2")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define cll const ll
#define lp(a, b, c) for(ll a = b; a <= c; ++a)
#define lpd(a, b, c) for(ll a = b; a >= c; --a)
#define vec(a) vector<a>
#define pp(a, b) pair<a, b>
#define EACHCASE lpd(cs, read(), 1)
#define Fname "mecho"
using namespace std;

template <typename T> inline void Read(T &x){
    x = 0; char c;
    ll dau = 1;
    while(!isdigit(c = getchar())) if(c == '-') dau = -1;
    do{
        x = x * 10 + c - '0';
    } while (isdigit(c = getchar()));
    x *= dau;
}

ll read(){
    ll tmp;
    cin >> tmp;
    return tmp;
}

void giuncute(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
}

void OF(){
    if(fopen(Fname".inp", "r")){
        freopen(Fname".inp", "r", stdin);
        freopen(Fname".out", "w", stdout);
    } else if(fopen(Fname".in", "r")){
        freopen(Fname".in", "r", stdin);
        freopen(Fname".out", "w", stdout);
    }
}

cll mxn = 805, dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
ll n, s, a[mxn][mxn], d[mxn][mxn];
pp(ll, ll) st, fi;
queue<pp(ll, ll)> q;

void bfs(ll i, ll j, ll step, const ll &ti){
    // if(step == s) return;
    // lp(t, 0, 3){
    //     ll ii = i + dx[t], jj = j + dy[t];
    //     if(a[ii][jj] == -1 || d[ii][jj]) continue;
    //     d[ii][jj] = ti;
    //     if(a[ii][jj] > ti) q.push({ii, jj});
    //     dfs(ii, jj, step + 1, ti);
    // }
    queue<pp(ll, ll)> qq[2];
    qq[0].push({i, j});
    while(qq[0].size()){
        if(++step > s) break;
        while(qq[0].size()){
            ll u = qq[0].front().first, v = qq[0].front().second;
            // if(i == 4 && j == 5) cerr << u << ' ' << v << '\n';
            qq[0].pop();
            lp(t, 0, 3){
                ll nu = u + dx[t], nv = v + dy[t];
                if(a[nu][nv] == -1 || (d[nu][nv] != d[u][v] && d[nu][nv] != 0)) continue;
                d[nu][nv] = d[u][v];
                if(a[nu][nv] > d[nu][nv]) q.push({nu, nv});
                qq[1].push({nu, nv});
            }
        }
        swap(qq[0], qq[1]);
    }
}

bool check(ll timestart){
    lp(i, 1, n) lp(j, 1, n) d[i][j] = 0;
    d[st.first][st.second] = timestart;
    q.push(st);
    while(q.size()){
        ll u = q.front().first, v = q.front().second;
        q.pop();
        lp(i, 0, 3){
            ll nu = u + dx[i], nv = v + dy[i];
            if(a[nu][nv] == -1 || (d[nu][nv] != 0 && d[nu][nv] != d[u][v] + 1)) continue;
            d[nu][nv] = d[u][v] + 1;
            // if(u == 4 && v == 4) cerr << nu << ' ' << nv << ' ' << d[nu][nv] << '\n';
            if(a[nu][nv] > d[nu][nv]) q.push({nu, nv});
            bfs(nu, nv, 1, d[nu][nv]);
        }   
    }
    // lp(i, 1, n){
    //     lp(j, 1, n) cerr << d[i][j] << ' ';
    //     cerr << '\n';
    // }
    if(d[fi.first][fi.second] == 0 || !d[fi.first][fi.second]) 
        return 0;
    return 1;
}

int main(){
    giuncute();
    #ifndef ONLINE_JUDGE
    OF();
    #endif
    memset(a, -1, sizeof a);
    memset(d, -1, sizeof d);
    cin >> n >> s;
    lp(i, 1, n) lp(j, 1, n){
        char c;
        cin >> c;
        a[i][j] = 0;
        if(c == 'M') st = {i, j};
        else if(c == 'D') fi = {i, j};
        else if(c == 'T') a[i][j] = -1;
        else if(c == 'H') q.push({i, j}), a[i][j] = 1;
    }
    while(q.size()){
        ll u = q.front().first, v = q.front().second;
        q.pop();
        lp(i, 0, 3){
            ll nu = u + dx[i], nv = v + dy[i];
            if(a[nu][nv] || (nu == fi.first && nv == fi.second)) continue;
            a[nu][nv] = a[u][v] + 1;
            q.push({nu, nv});
        }
    }
    ll l = 1, r = n * n, ans = -1; 
    while(l <= r){
        ll mid = (l + r) >> 1;
        if(check(mid)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    if(ans != -1) ans -= 1;
    cout << ans;
}

Compilation message (stderr)

mecho.cpp: In function 'void OF()':
mecho.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen(Fname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen(Fname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen(Fname".in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen(Fname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 100