Submission #583475

#TimeUsernameProblemLanguageResultExecution timeMemory
583475HeyYouNotYouYouMecho (IOI09_mecho)C++14
24 / 100
839 ms21128 KiB
#include <bits/stdc++.h> #define int long long #define endl '\n' using namespace std; const int N = 801,INF=1e12; int n , o, srcx, srcy, destx, desty, ar[N][N]; int dx[4]={0,-1,1,0}; int dy[4]={-1,0,0,1}; struct node{ int x, y, dist; }; bool valid1(int x, int y){ if(x>=0 && x<n && y>=0 && y<n && (x!=srcx || y!=srcy) && (x!=destx || y!=desty)) return true; return false; } bool valid(int x, int y){ if(x>=0 && x<n && y>=0 && y<n) return true; return false; } bool check(int mins) { vector<pair<int,int>>hives; int arr[n][n],arr2[n][n]; queue<pair<int,int>>q; int vis[n][n]; memset(vis,0,sizeof vis); for(int i = 0 ; i < n ; i ++) for(int j = 0 ; j < n ; j ++) { if(ar[i][j]==1){ q.push({i,j}); vis[i][j]=1; arr[i][j]=0; } } while(!q.empty()) { int curx=q.front().first; int cury=q.front().second; q.pop(); for(int i = 0 ; i < 4; i ++) { int gox = curx+dx[i], goy = cury+dy[i]; if(valid(gox,goy) && !vis[gox][goy] && ar[gox][goy]!=-1 && (destx!=gox || desty!=goy)){ vis[gox][goy]=1; arr[gox][goy]=arr[curx][cury]+1; q.push({gox,goy}); } } } queue<pair<int,int>>qq; memset(vis,0,sizeof vis); memset(arr2,0,sizeof arr2); qq.push({srcx,srcy}); vis[srcx][srcy]=1; if(arr[srcx][srcy]<=mins) return false; arr2[srcx][srcy]=0; while(!qq.empty()){ int curx=qq.front().first; int cury=qq.front().second; if(curx==destx&&cury==desty) return true; qq.pop(); for(int i = 0 ; i < 4; i ++) { int gox = curx+dx[i], goy = cury+dy[i]; if(valid(gox,goy) && !vis[gox][goy] && ar[gox][goy]!=-1){ if(arr[gox][goy] > floor((double)(arr2[curx][cury]+1)/(double)o)+mins){ // cout<<curx<<" "<<cury<<" "<<gox<<" "<<goy<<" "<<arr2[curx][cury]<<" "<<arr[gox][goy]-mins<<" "<<c<<" "<<arr2[curx][cury]+(c%o==0&&c>0)<<endl; vis[gox][goy]=1; arr2[gox][goy]=arr2[curx][cury]+1; qq.push({gox,goy}); } } } } return false; } int32_t main() { //freopen("abc.in", "r", stdin); cin >> n >> o; for(int i = 0 ; i < n ; i ++){ for(int j = 0 ; j < n ; j ++){ char x; cin >> x; ar[i][j] = (x=='H'?1:((x=='G'||x=='D'||x=='M')?0:-1)); if(x=='M') srcx=i, srcy=j; if(x=='D') destx=i, desty=j; } } int l = 0 , r = n*n; int ans=-1; while(l <= r) { int mid = (l+r)/2; // cout<<mid<<endl; if(check(mid)) { l = mid+1; ans=mid; } else { r = mid-1; } } cout<<ans<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...