제출 #501944

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
501944		lorenzoferrari	Mecho (IOI09_mecho)	C++17	0 / 100	37 ms	65540 KiB

mecho

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

int32_t main() {
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  int n, s;
  cin >> n >> s;
  vector<vector<char>> m(n, vector<char> (n));
  int xs, ys;
  int xe, ye;
  for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
    cin >> m[i][j];
    if (m[i][j] == 'M') xs = i, ys = j;
    if (m[i][j] == 'D') xe = i, ye = j;
  }
  queue<pair<int, int>> Q;
  vector<vector<int>> d(n, vector<int> (n, 1e9));
  for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
    if (m[i][j] == 'H') {
      d[i][j] = 0;
      Q.push({i, j});
    }
  }
  while (!Q.empty()) {
    auto [x, y] = Q.front();
    Q.pop();
    if (x     && (m[x-1][y  ] == 'G' || m[x-1][y  ] == 'M') && d[x-1][y  ] > d[x][y] + 1) d[x-1][y  ] = d[x][y] + 1, Q.push({x-1, y  });
    if (y     && (m[x  ][y-1] == 'G' || m[x  ][y-1] == 'M') && d[x  ][y-1] > d[x][y] + 1) d[x  ][y-1] = d[x][y] + 1, Q.push({x  , y-1});
    if (x<n-1 && (m[x+1][y  ] == 'G' || m[x+1][y  ] == 'M') && d[x+1][y  ] > d[x][y] + 1) d[x+1][y  ] = d[x][y] + 1, Q.push({x+1, y  });
    if (y<n-1 && (m[x  ][y+1] == 'G' || m[x  ][y+1] == 'M') && d[x  ][y+1] > d[x][y] + 1) d[x  ][y+1] = d[x][y] + 1, Q.push({x  , y+1});
  }
  auto psb = [&](int delay) {
    // bfs from mecho's location
    // it's possible iff dist_from_mecho[i][j]/s + delay < d[i][j]
    queue<pair<int, int>> Q;
    vector<vector<int>> dm(n, vector<int> (n, 1e9));
    Q.push({xs, ys});
    dm[xs][ys] = 0;
    while (!Q.empty()) {
      auto [x, y] = Q.front();
      Q.pop();
      if (delay + (dm[x][y]) / s >= d[x][y]) continue;
      if (x     && m[x-1][y  ] != 'T' && dm[x-1][y  ] > dm[x][y] + 1 && delay + (dm[x][y] + 1) / s < d[x-1][y  ]) dm[x-1][y  ] = dm[x][y] + 1, Q.push({x-1, y  });
      if (y     && m[x  ][y-1] != 'T' && dm[x  ][y-1] > dm[x][y] + 1 && delay + (dm[x][y] + 1) / s < d[x  ][y-1]) dm[x  ][y-1] = dm[x][y] + 1, Q.push({x  , y-1});
      if (x<n-1 && m[x+1][y  ] != 'T' && dm[x+1][y  ] > dm[x][y] + 1 && delay + (dm[x][y] + 1) / s < d[x+1][y  ]) dm[x+1][y  ] = dm[x][y] + 1, Q.push({x+1, y  });
      if (y<n-1 && m[x  ][y+1] != 'T' && dm[x  ][y+1] > dm[x][y] + 1 && delay + (dm[x][y] + 1) / s < d[x  ][y+1]) dm[x  ][y+1] = dm[x][y] + 1, Q.push({x  , y+1});
    }
    return dm[xe][ye] != 1e9;
  };
  int l = 0, r = n * n + 2;
  while (r - l > 1) {
    int mid = (l + r) / 2;
    if (psb(mid))
      l = mid;
    else
      r = mid;
  }
  cout << (psb(l) ? l : -1) << "\n";
}

컴파일 시 표준 에러 (stderr) 메시지

mecho.cpp: In function 'int32_t main()':
mecho.cpp:6:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 |   freopen("input.txt", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:7:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |   freopen("output.txt", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100