Submission #895617

#	Time	Username	Problem	Language	Result	Execution time	Memory
895617		lmkae	Mecho (IOI09_mecho)	C++14	18 / 100	398 ms	22312 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
const int INF = 9000372036854775800;
 
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define print(arr) for (auto i : arr) cout << i << " "; cout << endl;
typedef vector<vector<int>> vvi;
typedef vector<pair<int, int>> vpi;
typedef vector<int> vi;
typedef pair<int, int> pii;
 
void setFile(string name) {
  freopen((name + "in.txt").c_str(), "r", stdin);
  freopen((name + "out.txt").c_str(), "w", stdout);
}
 
int MOD = 1e9 + 7;
int n, s;

pii pot, home;

bool f(int sleep, vvi dists) {
  int n = dists.size();
  rep(i, 0, n) {
    rep(j, 0, n) {
      if (dists[i][j] == INF) continue;
      dists[i][j] -= sleep;
      if (dists[i][j] <= 0) dists[i][j] = INF;
    }
  }

  // check if valid path exists
  vector<vector<bool>> visited(n, vector<bool>(n, false));
  queue<vi> q;
  q.push({pot.first, pot.second});
  visited[pot.first][pot.second] = true;
  while (!q.empty()) {
    vi curr = q.front(); q.pop();
    if (abs(home.first - curr[0]) + abs(home.second - curr[1]) <= s) return true;
    vpi dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    trav(d, dir) {
      int x = curr[0] + d.first, y = curr[1] + d.second;
      if (x < 0 || x >= n || y < 0 || y >= n) continue;
      if (visited[x][y]) continue;
      if (dists[x][y] == INF) continue;
      visited[x][y] = true;
      q.push({x, y});
    }
  }
  return false;
}

int last_true_jump(int lo, int hi, vvi &dists) {
	lo--;
	for (int dif = hi - lo; dif > 0; dif /= 2) {
		while (lo + dif <= hi && f(lo + dif, dists)) { lo += dif; }
	}
	return lo;
}
 
signed main() {
  
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> s;
  queue<vi> hives;
  vector<vector<char>> grid(n, vector<char>(n));
  vvi beedist(n, vi(n, INF));
  rep(i, 0, n) {
    rep(j, 0, n) {
      cin >> grid[i][j];
      if (grid[i][j] == 'M') {
        pot = {i, j};
      } else if (grid[i][j] == 'D') {
        home = {i, j};
      } else if (grid[i][j] == 'H') {
        hives.push({i, j, 0});
        beedist[i][j] = 0;
      }
    }
  }

  vpi dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  while (!hives.empty()) {
    vi curr = hives.front(); hives.pop();
    trav(d, dir) {
      int x = curr[0] + d.first, y = curr[1] + d.second;
      if (x < 0 || x >= n || y < 0 || y >= n) continue;
      if (grid[x][y] == 'T' || grid[x][y] == 'D') continue;
      if (beedist[x][y] > curr[2] + 1) {
        beedist[x][y] = curr[2] + 1;
        hives.push({x, y, curr[2] + 1});
      }
    }
  }

  vvi mydist(n, vi(n, INF));
  queue<vi> q;
  q.push({pot.first, pot.second, 0});
  mydist[pot.first][pot.second] = 0;
  while (!q.empty()) {
    vi curr = q.front(); q.pop();
    trav(d, dir) {
      int x = curr[0] + d.first, y = curr[1] + d.second;
      if (x < 0 || x >= n || y < 0 || y >= n) continue;
      if (grid[x][y] == 'T') continue;
      if (mydist[x][y] > curr[2] + 1) {
        mydist[x][y] = curr[2] + 1;
        q.push({x, y, curr[2] + 1});
      }
    }
  }
  vvi dists(n, vi(n, INF));
  rep(i, 0, n) {
    rep(j, 0, n) {
      if (mydist[i][j] == INF) {
        dists[i][j] = INF;
        continue;
      } if (mydist[i][j] == 0) continue;
      
      if (mydist[i][j] % s == 0) {
        mydist[i][j] /= s;
      } else {
        mydist[i][j] /= s;
        mydist[i][j]++;
      }
      dists[i][j] = beedist[i][j] - mydist[i][j];
    }
  }

  // trav(row, dists) {
  //   trav(i, row) {
  //     if (i == INF) cout << "-1 ";
  //     else cout << i << " ";
  //   }
  //   cout << endl;
  // }

  int ans = last_true_jump(0, n*n, dists);
  cout << ans << endl;

  




  
  
}

Compilation message (stderr)

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

• Subtask 1: 18 / 100