Submission #1092620

#TimeUsernameProblemLanguageResultExecution timeMemory
10926204QT0RMecho (IOI09_mecho)C++17
60 / 100
134 ms7008 KiB
#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 timeMemoryGrader output
Fetching results...