Submission #500005

#	Time	Username	Problem	Language	Result	Execution time	Memory
500005		Nartifact	Mecho (IOI09_mecho)	C++14	30 / 100	209 ms	13320 KiB

mecho

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define forinc(i,a,b) for(int i=a;i<=b;++i)
#define fordec(i,a,b) for(int i=a;i>=b;--i)
#define pb push_back
#define eb emplace_back
#define pii pair <int,int>
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int N = 888, inf = 1e15;
const int H[] = {1, 0, -1, 0};
const int C[] = {0, 1, 0, -1};
int n, s, cti = inf;
char a[N][N];
int t[N][N], mec[N][N];
pii sta, fin;

bool valid (const int& x, const int& y)
{
    return x && y && x <= n && y <= n
          && a[x][y] != 'T';
}

bool ok (const int& tg)
{
    queue <pii> q;
    q.push(sta);
    forinc(i,1,n) forinc(j,1,n) mec[i][j] = inf;
    mec[sta.fi][sta.se] = 0;
    while(q.size()) {
        auto x = q.front(); q.pop();
        if(x == fin) return 1;
        forinc(i,0,3) {
            int nh = x.fi + H[i];
            int nc = x.se + C[i];
            if(valid(nh, nc) && mec[nh][nc] > mec[x.fi][x.se] + 1) {
                int gap = (mec[x.fi][x.se] + 1) / s;
                if((mec[x.fi][x.se] + 1) % s) gap++;
                if(gap <= t[nh][nc] - tg) {
                    mec[nh][nc] = mec[x.fi][x.se] + 1;
                    q.push({nh, nc});
                }
            }
        }
    }
    return 0;
}

void solve ()
{
    queue <pii> q;
    forinc(i,1,n) forinc(j,1,n) {
        t[i][j] = inf;
        if(a[i][j] == 'H') {
            q.push({i, j});
            t[i][j] = 0;
        }
        else if(a[i][j] == 'M') {
            sta = {i, j};
            t[i][j] = -1;
        }
        else if(a[i][j] == 'D')
            fin = {i, j};
    }

    // bfs bee
    while(q.size()) {
        auto x = q.front(); q.pop();
        forinc(i,0,3) {
            int nh = x.fi + H[i];
            int nc = x.se + C[i];
            if(valid(nh, nc) && t[nh][nc] > t[x.fi][x.se] + 1) {
                t[nh][nc] = t[x.fi][x.se] + 1;
                q.push({nh, nc});
            }
        }
    }

    // binary search
    int l = 0, r = n * n, ans = -1;
    while(l <= r) {
        int mid = l + r >> 1;
        if(ok(mid)) {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    cout << ans;
}

void read ()
{
    cin >> n >> s;
    forinc(i,1,n) forinc(j,1,n)
        cin >> a[i][j];
    solve();
}

main ()
{
	#define task "ioi09_mecho"
	cin.tie(0) -> sync_with_stdio(0);
	if(fopen (task ".inp", "r")) {
		freopen (task ".inp", "r", stdin);
		freopen (task ".out", "w", stdout);
	}
    read();
	return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'void solve()':
mecho.cpp:88:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |         int mid = l + r >> 1;
      |                   ~~^~~
mecho.cpp: At global scope:
mecho.cpp:106:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  106 | main ()
      | ^~~~
mecho.cpp: In function 'int main()':
mecho.cpp:111:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   freopen (task ".inp", "r", stdin);
      |   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:112:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   freopen (task ".out", "w", stdout);
      |   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 100