Submission #1154687

#TimeUsernameProblemLanguageResultExecution timeMemory
1154687murpylMecho (IOI09_mecho)C++20
38 / 100
322 ms6980 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; #define pb push_back #define rsz resize #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() using pi = pair<int,int>; #define endl "\n" #define mp make_pair void setIO(string name = "") { ios_base::sync_with_stdio(0); cin.tie(0); if(sz(name)){ freopen((name+".in").c_str(), "r", stdin); freopen((name+".out").c_str(), "w", stdout); } } const int inf = 1e9; const int maxn = 808; int n, s; char grid[maxn][maxn]; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; vector<vi> dist(maxn, vi(maxn, inf)); vector<vi> beardist(maxn, vi(maxn, inf)); int sx, sy, ex, ey; bool reachable(int mid){ for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++){ beardist[i][j] = inf; } } priority_queue<pair<int, pi>, vector<pair<int, pi>>, greater<pair<int, pi>>> pq; beardist[sx][sy] = 0; pq.push({0, {sx, sy}}); while (!pq.empty()){ auto [d, p] = pq.top(); pq.pop(); int time = mid+ d/s; auto [x, y] = p; if (beardist[x][y] < d) continue; for (int i = 0; i < 4; i++){ int nx = x+dx[i]; int ny = y+dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; if (grid[nx][ny] == 'T' || grid[nx][ny] == 'H') continue; if (time >= dist[nx][ny]) continue; if (beardist[nx][ny] > d+1){ beardist[nx][ny] = d+1; pq.push({d+1, {nx, ny}}); } } } return beardist[ex][ey]!=inf; } int main(){ setIO(); cin>>n>>s; priority_queue<pair<int, pi>, vector<pair<int, pi>>, greater<pair<int, pi>>> pq; for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++){ cin>>grid[i][j]; if (grid[i][j] == 'H'){ pq.push({0, {i, j}}); dist[i][j] = 0; } if (grid[i][j] == 'M'){ sx = i; sy = j; } if (grid[i][j] == 'D'){ ex = i; ey = j; } } } while (!pq.empty()){ auto [d, p] = pq.top(); pq.pop(); auto [x, y] = p; if (dist[x][y] < d) continue; for (int i = 0; i < 4; i++){ int nx = x+dx[i]; int ny = y+dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; if (grid[nx][ny] == 'T' || grid[nx][ny] == 'D') continue; if (dist[nx][ny] > d+1){ dist[nx][ny] = d+1; pq.push({d+1, {nx, ny}}); } } } if (!reachable(0)){ cout<<-1<<endl; return 0; } int l = 0, r = n*n; while (l < r){ int mid = (l+r)/2; if (!reachable(mid)){ r = mid; } else{ l = mid+1; } } cout<<l-1<<endl; }

Compilation message (stderr)

mecho.cpp: In function 'void setIO(std::string)':
mecho.cpp:15:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |                 freopen((name+".in").c_str(), "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen((name+".out").c_str(), "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...