제출 #583170

#제출 시각아이디문제언어결과실행 시간메모리
583170HeyYouNotYouYouMecho (IOI09_mecho)C++14
22 / 100
697 ms16096 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]; for(int i = 0 ; i < n ; i ++) for(int j = 0 ; j < n ; j ++) { arr[i][j]=ar[i][j]; if(arr[i][j]==1) hives.push_back({i,j}); } queue<pair<int,int>>q; int vis[n][n]; memset(vis,0,sizeof vis); for(auto e : hives){ q.push({e.first,e.second}); vis[e.first][e.second]=1; } 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] && !arr[gox][goy]){ vis[gox][goy]=1; arr[gox][goy]=arr[curx][cury]+1; q.push({gox,goy}); } } } memset(vis,0,sizeof vis); q.push({srcx,srcy}); if(arr[srcx][srcy]<=mins) return false; vis[srcx][srcy]=1; arr[srcx][srcy]=1; while(!q.empty()){ int curx=q.front().first; int cury=q.front().second; if(curx==destx&&cury==desty) return true; 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] && arr[gox][goy]!=-1){ if(mins+(((arr[curx][cury])-1)/o)+1 < arr[gox][goy]){ vis[gox][goy]=1; arr[gox][goy]=arr[curx][cury]+1; q.push({gox,goy}); } } } } return false; } int32_t main() { //freopen("abc.in", "r", stdin); cin >> n >> o; int id[n][n]; 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 = 1 , r = n*n+1; int ans=-1; while(l <= r) { int mid = (l+r)/2; if(check(mid)) { l = mid+1; ans=mid; } else { r = mid-1; } } cout<<ans<<endl; }

컴파일 시 표준 에러 (stderr) 메시지

mecho.cpp: In function 'int32_t main()':
mecho.cpp:86:7: warning: unused variable 'id' [-Wunused-variable]
   86 |   int id[n][n];
      |       ^~
#Verdict Execution timeMemoryGrader output
Fetching results...