Submission #1224057

#TimeUsernameProblemLanguageResultExecution timeMemory
1224057enzyMecho (IOI09_mecho)C++20
57 / 100
139 ms13384 KiB
#include<bits/stdc++.h> using namespace std; const int maxn=810; int marc[maxn][maxn], db[maxn][maxn], mb[maxn][maxn], dx[]={1,-1,0,0}, dy[]={0,0,1,-1}, dist[maxn][maxn], m[maxn][maxn], n; bool in(int x, int y){ return 1<=x&&x<=n&&1<=y&&y<=n; } bool check(int tmp, int ix, int iy, int fx, int fy, int s){ queue<pair<int,int>>q; q.push({ix,iy}); memset(dist,-1,sizeof(dist)); memset(m,0,sizeof(m)); dist[ix][iy]=tmp*s; m[ix][iy]++; while(!q.empty()){ int x=q.front().first, y=q.front().second, w=dist[x][y]; q.pop(); w++; int at=w/s; for(int i=0;i<4;i++){ int nx=x+dx[i], ny=y+dy[i]; if(in(nx,ny)&&!marc[nx][ny]&&!m[nx][ny]&&at<db[nx][ny]){ m[nx][ny]++; dist[nx][ny]=w; q.push({nx,ny}); } } } return dist[fx][fy]!=-1; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int s; cin >> n >> s; queue<pair<int,int>>bees; int ix, iy, fx, fy; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ char c; cin >> c; if(c=='T') marc[i][j]=-1; if(c=='H'){ bees.push({i,j}); mb[i][j]++; } if(c=='M'){ ix=i; iy=j; } if(c=='D'){ fx=i; fy=j; } } while(!bees.empty()){ int x=bees.front().first, y=bees.front().second; bees.pop(); for(int i=0;i<4;i++){ int nx=x+dx[i], ny=y+dy[i]; if(in(nx,ny)&&!mb[nx][ny]&&!marc[nx][ny]){ db[nx][ny]=db[x][y]+1; mb[nx][ny]++; bees.push({nx,ny}); } } } /*for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) cout << db[i][j] << " "; cout << endl; } cout << endl;*/ int l=0, r=maxn*maxn; while(l<r){ int mid=(l+r+1)/2; if(check(mid,ix,iy,fx,fy,s)) l=mid; else r=mid-1; } //bool lx=check(1,ix,iy,fx,fy,s); /*for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) cout << dist[i][j] << " "; cout << endl; }*/ cout << l << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...