Submission #958047

#TimeUsernameProblemLanguageResultExecution timeMemory
958047theehannMecho (IOI09_mecho)C++17
69 / 100
150 ms11712 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll #define ft first #define se second #define NAME "A" #define file freopen(NAME".INP","r",stdin); freopen(NAME".OUT","w",stdout); #define sdf ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); const int MOD = 1e9 + 7; const int N = 800 + 5, INF = 1e15; int dx[4] = {0, 0, -1, 1}; int dy[4] = {-1, 1, 0, 0}; char a[N][N]; int dis[N][N], vis[N][N] = {INF}; bool f = false; int n, step, homex, homey, mx, my; bool bfs(int len, int x, int y){ vis[x][y] = len; queue<tuple<int, int, int>> q; q.push({x, y, 0}); while(!q.empty()){ const auto [sx, sy, cur] = q.front(); q.pop(); int dist = (cur + 1) / step; for(int i = 0;i < 4;++i){ int u = sx + dx[i], v = sy + dy[i]; if(u < 1 || v < 1 || v > n || u > n) continue; if(a[u][v] == 'G' && (cur + 1) < vis[u][v] && dist < dis[u][v] - (len / step)){ vis[u][v] = cur + 1; q.push({u, v, cur + 1}); } } } for(int i = 0;i < 4;++i){ int u = homex + dx[i], v = homey + dy[i]; if(vis[u][v] != INF && (a[u][v] == 'G' || a[u][v] == 'M') && vis[u][v] / step < dis[u][v] - (len / step)){ return true; } } return false; } int32_t main(){ sdf cin >> n >> step; queue<pair<int, int>> q; for(int i = 1;i <= n;++i){ for(int j = 1;j <= n;++j){ cin >> a[i][j]; dis[i][j] = INF; if(a[i][j] == 'H'){ q.push({i, j}); dis[i][j] = 0; } else if(a[i][j] == 'D'){ homex = i; homey = j; } else if(a[i][j] == 'M'){ mx = i; my = j; } } } while(!q.empty()){ const auto [x, y] = q.front(); q.pop(); for(int i = 0;i < 4;++i){ int u = x + dx[i]; int v = y + dy[i]; if(u < 1 || v < 1 || u > n || v > n) continue; if(dis[u][v] == INF && (a[u][v] == 'G' || a[u][v] == 'M')){ dis[u][v] = dis[x][y] + 1; q.push({u, v}); } } } int l = 1, r = INF; int ans =0; while(l <= r){ int mid = (l + r) / 2; for(int i = 1;i <= n;++i){ for(int j = 1;j <= n;++j){ vis[i][j] = INF; } } if(bfs(mid * step, mx, my)){ l = mid + 1; ans = mid; } else{ r = mid - 1; } } cout << ((ans >= 1) ? ans : -1) ; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...