Submission #948118

#TimeUsernameProblemLanguageResultExecution timeMemory
948118packmaniMecho (IOI09_mecho)C++14
100 / 100
161 ms7300 KiB
#include<bits/stdc++.h> using namespace std; #define int long long int int n,speed; char inp[805][805]; int board[805][805]; bool visited[805][805]; queue<pair<int,int>> q; pair<int,int> s,e; int cr,cc,er,ec; int dr[]={0,-1,0,1}; int dc[]={1,0,-1,0}; int maxTime=0; int l,m,r; int layer,tillNext,inNext; bool bfs(int start) { queue<pair<int,int>> tempq; memset(visited,0,sizeof(visited)); int time=start; if(time>=board[s.first][s.second]) return 0; tempq.push({s.first,s.second}); tillNext=1; inNext=0; layer=0; while(!tempq.empty()) { cr = tempq.front().first; cc = tempq.front().second; tempq.pop(); if(board[cr][cc]>time or inp[cr][cc]=='M')//bees have not reached this spot yet { for(int i=0;i<4;i++) { er = cr + dr[i]; ec = cc + dc[i]; if(er<0 or ec<0 or er>=n or ec>=n) continue; if(inp[er][ec]=='D') return 1; if(visited[er][ec]) continue; if(board[er][ec]==-1) continue; if(board[er][ec]<=time) continue; tempq.push({er,ec}); visited[er][ec]=1; inNext++; } } tillNext--; if(tillNext==0) { tillNext = inNext; inNext = 0; layer++; if(layer%speed==0) time++; } } return 0; } int32_t main() { cin.tie(0); ios_base::sync_with_stdio(false); cin >> n >> speed; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { cin >> inp[i][j]; if(inp[i][j]=='T') board[i][j]=-1; //no one can traverse if(inp[i][j]=='H') { board[i][j]=0; //not walkable since the 0th sec q.push({i,j}); } if(inp[i][j]=='M') { s={i,j}; board[i][j]=1000000; } if(inp[i][j]=='D') e={i,j}; if(inp[i][j]=='G') board[i][j] = 1000000; } } //bees while(!q.empty()) { cr = q.front().first; cc = q.front().second; q.pop(); for(int i=0;i<4;i++) { er = cr + dr[i]; ec = cc + dc[i]; if(er<0 or ec<0 or er>=n or ec>=n) continue; if(board[er][ec]==-1 or board[er][ec]=='D') continue; if(board[er][ec]<=board[cr][cc]+1) continue; board[er][ec]=board[cr][cc]+1; q.push({er,ec}); maxTime=max(maxTime,board[er][ec]); } } l=0; r=n*n; m = l + (r-l)/2; int ans=-1; while(l<=r) { if(bfs(m)==1) { l=m+1; ans=m; } else r=m-1; m = l + (r+0.5-l)/2; } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...