Submission #767740

#	Time	Username	Problem	Language	Result	Execution time	Memory
767740		mgl_diamond	Mecho (IOI09_mecho)	C++14	100 / 100	398 ms	4408 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using il = pair<ll, ll>;

#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

void setIO(string name) {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  if (!name.empty()) {
    freopen((name + ".in").c_str(), "r", stdin);
    freopen((name + ".out").c_str(), "w", stdout);
  }
}

const int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
const int LIM = 1e9;
const int N = 808;

int n, s, vi[N][N];
ii st, en;
vector<ii> hives;
char a[N][N];

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

void propaganda(vector<ii> &lst, int xet, int dis) {
  queue<pair<ii, int>> bfs;
  for(auto x : lst) bfs.push({x, 0});
  lst.clear();
  
  while (!bfs.empty()) {
    auto at = bfs.front(); bfs.pop();
    int x = at.fi.fi, y = at.fi.se;

    if (vi[x][y] == 2 && xet == 1) {
      continue;
    }

    if (at.se == dis) {
      lst.emplace_back(at.fi);
      continue;
    }

    foru(d, 0, 3) {
      int nx = x+dx[d], ny = y+dy[d];
      if (!e(nx, ny) || a[nx][ny] == 'T') continue;
      if (xet == 2 && a[nx][ny] == 'D') continue;
      if (vi[nx][ny] != 0) {
        if (xet == 1) continue;
        if (vi[nx][ny] == 2) continue; 
      }
      vi[nx][ny] = xet;
      bfs.push({{nx, ny}, at.se+1});
    }
  }
}

void out() {
  foru(i, 1, n) {
    foru(j, 1, n) cout << vi[i][j] << " ";
    cout << "\n";
  }
  cout << "---------\n";
}

bool can(int eat_time) {
  memset(vi, 0, sizeof(vi));
  vector<ii> me, bees;
  me.emplace_back(st);
  bees = hives;
  propaganda(bees, 2, eat_time);
  while (!me.empty()) {
    propaganda(me, 1, s);
    propaganda(bees, 2, 1);
  }
  return vi[en.fi][en.se] == 1;
}

int main() {
  setIO("");

  cin >> n >> s;
  foru(i, 1, n)
    foru(j, 1, n) {
      cin >> a[i][j];
      if (a[i][j] == 'M') st = {i, j};
      else if (a[i][j] == 'D') en = {i, j};
      else if (a[i][j] == 'H') hives.emplace_back(i, j);
    }

  int ans = -1;
  for(int z=n*n; z>0; z>>=1) 
    while (ans+z <= n*n && can(ans+z))
      ans += z;
  
  cout << ans;
}

Compilation message (stderr)

mecho.cpp: In function 'void setIO(std::string)':
mecho.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     freopen((name + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen((name + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100