Submission #155437

#	Time	Username	Problem	Language	Result	Execution time	Memory
155437		karma	Mecho (IOI09_mecho)	C++14	100 / 100	826 ms	6676 KiB

mecho

#include<bits/stdc++.h>
#define pb      emplace_back
#define mp      make_pair
#define fi      first
#define se      second
#define ll      long long

using namespace std;

//T cay, M pos, D nha, G co, H ong

const int N = 803;
const int oo = int(1e9);
typedef pair<int, int> pii;

int lv[N][N], n, s;
bool vis[N][N];
string a[N], org[N];
queue<pii> q;
vector<pii> honey, cur, _cur, _honey;
pii st, en;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

bool Inside(int i, int j) {return i >= 1 && i <= n && j >= 1 && j <= n;}

int deg(int i, int j) {
    int x = 0; pii nxt;
    for(int k = 0; k < 4; ++k) {
        nxt = mp(i + dx[k], j + dy[k]);
        if(Inside(nxt.fi, nxt.se) && a[nxt.fi][nxt.se] != 'H'
                && a[nxt.fi][nxt.se] != 'T' && a[nxt.fi][nxt.se] != 'D') ++x;
    }
    return x;
}

bool Check(int mid) {
    pii top, nxt;
    while(q.size()) q.pop();
    for(int i = 1; i <= n; ++i) {
        a[i] = org[i];
        for(int j = 1; j <= n; ++j) {
            if(a[i][j] == 'H') q.push(mp(i, j));
            lv[i][j] = 0;
            if(a[i][j] == 'T' || a[i][j] == 'H') vis[i][j] = 1;
            else vis[i][j] = 0;
        }
    }
    if(mid) {
        while(q.size()) {
            top = q.front(); q.pop();
            for(int i = 0; i < 4; ++i) {
               nxt = mp(top.fi + dx[i], top.se + dy[i]);
               if(Inside(nxt.fi, nxt.se) && !vis[nxt.fi][nxt.se] && a[nxt.fi][nxt.se] != 'D') {
                  if((lv[nxt.fi][nxt.se] = lv[top.fi][top.se] + 1) < mid) q.push(nxt);
                  a[nxt.fi][nxt.se] = 'H'; vis[nxt.fi][nxt.se] = 1;
               }
            }
        }
    }
    _honey.clear();
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            if(a[i][j] == 'H') {
               if(deg(i, j)) _honey.pb(i, j);
            }
        }
    }
    if(a[st.fi][st.se] == 'H') return 0;
    _cur.clear(); _cur.pb(st); bool can = 1; vis[st.fi][st.se] = 1;
    while(can) { can = 0;
       for(int j = 1; j <= s; ++j) {
           if(_cur.empty()) break;
           cur.clear(); cur = _cur; _cur.clear(); can = 1;
           for(pii p: cur) {
              if(a[p.fi][p.se] == 'H') continue;
              for(int k = 0; k < 4; ++k) {
                 nxt = mp(p.fi + dx[k], p.se + dy[k]);
                 if(Inside(nxt.fi, nxt.se) && !vis[nxt.fi][nxt.se]) {
                    vis[nxt.fi][nxt.se] = 1; _cur.pb(nxt);
                    if(nxt == en) return 1;
                 }
              }
           }
       }
       honey.clear(); honey = _honey, _honey.clear();
       for(pii p: honey) {
          for(int k = 0; k < 4; ++k) {
             nxt = mp(p.fi + dx[k], p.se + dy[k]);
             if(Inside(nxt.fi, nxt.se) && a[nxt.fi][nxt.se] != 'H' && a[nxt.fi][nxt.se] != 'T' && a[nxt.fi][nxt.se] != 'D') {
                if(deg(nxt.fi, nxt.se)) _honey.pb(nxt);
                vis[nxt.fi][nxt.se] = 1; a[nxt.fi][nxt.se] = 'H';
             }
          }
       }
    }
    return 0;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    if(fopen("honey.inp", "r")) {
        freopen("honey.inp", "r", stdin);
        freopen("honey.out", "w", stdout);
    }
    cin >> n >> s;
    for(int i = 1; i <= n; ++i) {
        cin >> org[i]; org[i] = ' ' + org[i];
        for(int j = 1; j <= n; ++j) {
            if(org[i][j] == 'M') st = mp(i, j);
            if(org[i][j] == 'D') en = mp(i, j);
        }
    }
    int low = 0, high = int(n * n * 2), mid;
    while(low <= high) {
        mid = (low + high) >> 1;
        if(Check(mid)) low = mid + 1;
        else high = mid - 1;
    }
    cout << high;
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100