Submission #499705

#	Time	Username	Problem	Language	Result	Execution time	Memory
499705		tphuc2908	Mecho (IOI09_mecho)	C++14	97 / 100	187 ms	6312 KiB

mecho

#include<bits/stdc++.h>

using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
#define rep(i, x, y) for(int i = x; i <= y; ++i)
#define repi(i,x,y) for(int i = x; i >= y; --i)
#define ci(x) int x; cin>> x
#define TC(t) ci(t); while(t--)
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define cii(x, y) ci(x); ci(y)
#define ciii(x, y, z) ci(x); ci(y); ci(z)
#define mp make_pair
//#define int long long
typedef long long ll;
typedef vector<int> vi;
const int N = 8e2 + 5;
const int mod = 1e9 + 7;
const int mod1 = 1e9 + 9;
const int pi = 31;
const int inf = 1e9 + 5;
const int block = 330;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};

void readfile(){
    #ifdef ONLINE_JUDGE
    #else
        freopen("text.inp", "r", stdin);
    #endif // ONLINE_JUDGE
//    freopen("gravity.in", "r", stdin);
//    freopen("gravity.out", "w", stdout);
}

int n, s;
char a[N][N];
pair<int,int> st, e;

void inp(){
    cin >> n >> s;
    rep(i,1,n)
        rep(j,1,n){
            cin >> a[i][j];
            if(a[i][j]=='M')
                st = mp(i, j);
            if(a[i][j]=='D')
                e = mp(i, j);
        }
}

int d[N][N], d1[N][N];

void bfs_multi_source(){
    queue<pair<int,int> > q;
    rep(i,1,n)
        rep(j,1,n){
            d1[i][j] = inf;
            if(a[i][j]=='H')
                q.push(mp(i ,j)), d1[i][j] = 0;
        }
    while(!q.empty()){
        pair<int,int> top = q.front();
        q.pop();
        rep(i,0,3){
            int x = top.fi + dx[i];
            int y = top.se + dy[i];
            if(1 <= x && x <= n && 1 <= y && y <= n && a[x][y]!='T' && a[x][y]!='D' && d1[x][y] > d1[top.fi][top.se] + 1){
                d1[x][y] = d1[top.fi][top.se] + 1;
                q.push(mp(x,y));
            }
        }
    }
}

void bfs(int x, int y, int ti){
    rep(i,1,n)
        rep(j,1,n)
            d[i][j] = inf;
    queue<pair<int,int> > q;
    q.push(mp(x, y));
    d[x][y] = ti;
    if(ti >= d1[x][y]) return;
    bool ok = 1;
    while(!q.empty()){
        auto top = q.front();
        q.pop();
        rep(i,0,3){
            int x = top.fi + dx[i];
            int y = top.se + dy[i];
            if(1 <= x && x <= n && 1 <= y && y <= n && a[x][y]!='T' && d[x][y] > d[top.fi][top.se] + 1){
                d[x][y] = d[top.fi][top.se] + 1;
                int diff = d[x][y] - ti - 1;
                diff /= s;
                diff += ti + 1;
                if(diff < d1[x][y] || (diff==d1[x][y] && d[x][y] - d[top.fi][top.se] < s))
                    q.push(mp(x, y));
                else if(x==e.fi && y==e.se){
                        d[x][y] = inf;
                        ok = 0;
                        break;
                    }
            }
        }
        if(!ok) break;
    }
}

void process(){
    bfs_multi_source();
    int l = 0, r = n*n + 1, res = -1;
    while(l <= r){
        int mid = (l + r) >> 1;
        bfs(st.fi, st.se, mid);
        if(d[e.fi][e.se]==inf)
            r = mid - 1;
        else{
            res = mid;
            l = mid + 1;
        }
    }
    cout << res;
}

int main() {
   // readfile();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    TC(t){
        inp();
        process();
//    }
    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'void readfile()':
mecho.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         freopen("text.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 97 / 100