# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1092620 | 4QT0R | Mecho (IOI09_mecho) | C++17 | 134 ms | 7008 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
char tab[802][802];
int xcor[4]={0,1,0,-1};
int ycor[4]={1,0,-1,0};
int dist[802][802];
int oo=1e9;
int n,s;
void prep(){
queue<pii> q;
for (int i = 1; i<=n; i++){
for (int j = 1; j<=n; j++){
dist[i][j]=oo;
if (tab[i][j]=='H'){
q.push({i,j});
dist[i][j]=0;
}
}
}
while(q.size()){
auto [x,y]=q.front();
q.pop();
for (int i = 0; i<4; i++){
int u=x+xcor[i];
int v=y+ycor[i];
if (tab[u][v]=='G' && dist[u][v]>dist[x][y]+1){
dist[u][v]=dist[x][y]+1;
q.push({u,v});
}
}
}
}
int vis[802][802];
int iter=0;
pii st,nd;
bool bfs(int waiting){
queue<pair<pii,int>> q;
if (dist[st.first][st.second]<=waiting)return false;
q.push({st,0});
while(q.size()){
auto [pol,d]=q.front();
if (pol==nd)return true;
q.pop();
for (int i = 0; i<4; i++){
int u=pol.first+xcor[i];
int v=pol.second+ycor[i];
if ((tab[u][v]=='G'||tab[u][v]=='D') && vis[u][v]!=iter && (dist[u][v]>waiting+(d+1)/s)){
vis[u][v]=iter;
q.push({{u,v},d+1});
}
}
}
return false;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> s;
for (int i = 1; i<=n; i++){
for (int j = 1; j<=n; j++){
cin >> tab[i][j];
if (tab[i][j]=='M')st={i,j};
if (tab[i][j]=='D')nd={i,j};
}
}
prep();
int l=-1,p=1e4,md;
while(l<p){
md=(l+p+1)/2;
iter++;
if (bfs(md))l=md;
else p=md-1;
}
cout << l << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |