제출 #335551

#제출 시각아이디문제언어결과실행 시간메모리
335551batjargala11Mecho (IOI09_mecho)C++14
100 / 100
264 ms12396 KiB
#include <bits/stdc++.h> #define x first #define y second #define mp make_pair using namespace std; int n, s; pair<int, int> start, home; int T, H; int occ_time[805][805]; bool vis[805][805]; bool tree[805][805]; pair<int, int > Q[1000000]; int movex[] = {0, 0, -1, 1}; int movey[] = {-1, 1, 0, 0}; bool check(pair<int, int> v){ if(v.x >= 0 && v.x < n && v.y >= 0 && v.y < n && !tree[v.x][v.y] && !vis[v.x][v.y]) return 1; return 0; } void init_bfs(){ pair<int, int> u, v; while(H < T){ u = Q[H++]; if(u == home) continue; //cout << u.x << ' ' << u.y << ' ' << occ_time[u.x][u.y] << endl; for(int i = 0; i < 4; i++){ v = mp(u.x + movex[i], u.y + movey[i]); if(!check(v)) continue; occ_time[v.x][v.y] = occ_time[u.x][u.y] + s; vis[v.x][v.y] = 1; Q[T++] = v; } } } int dist[805][805]; bool solve(int st){ memset(vis, 0, sizeof(vis)); H = T = 0; pair<int, int> u, v; dist[start.x][start.y] = st; Q[T++] = start; while(H < T){ u = Q[H++]; if(u == home) return 1; if(dist[u.x][u.y] >= occ_time[u.x][u.y]) continue; for(int i = 0; i < 4; i++){ v = mp(u.x + movex[i], u.y + movey[i]); if(!check(v)) continue; dist[v.x][v.y] = dist[u.x][u.y] + 1; vis[v.x][v.y] = 1; Q[T++] = v; } } return 0; } int search(){ int l = 0, r = 800 * 800 + 1; int res = -1; while(l <= r){ int mid = (l + r) / 2; //cout << mid << endl; if(solve(mid * s)){ l = mid + 1; res = max(res, mid); } else r = mid - 1; } return res; } int main(){ cin >> n >> s; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++){ char ch; cin >> ch; if(ch == 'M') { start = mp(i, j); } if(ch == 'D') { home = mp(i, j); } if(ch == 'H') { Q[T++] = make_pair(i, j); vis[i][j] = 1; occ_time[i][j] = 0; } if(ch == 'T') { tree[i][j] = 1; } } init_bfs(); cout << search() << endl; return 0; }

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

mecho.cpp: In function 'int main()':
mecho.cpp:79:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   79 |   for(int i = 0; i < n; i++)
      |   ^~~
mecho.cpp:98:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   98 |     init_bfs();
      |     ^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...