제출 #521191

#제출 시각아이디문제언어결과실행 시간메모리
521191zhangjishenMecho (IOI09_mecho)C++98
100 / 100
188 ms6268 KiB
#include<bits/stdc++.h> using namespace std; #define mp make_pair #define pb push_back #define fi first #define se second template<typename T> bool chkmin(T &a, T b){return b < a ? a = b, 1 : 0;} template<typename T> bool chkmax(T &a, T b){return b > a ? a = b, 1 : 0;} typedef pair<int, int> pii; typedef long long ll; const int MAXN = 810, inf = 1e9; const int mv[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; int n, s, mx, my, dx, dy, d1[MAXN][MAXN], d2[MAXN][MAXN]; char g[MAXN][MAXN]; // bfs bool valid(int x, int y){ return x >= 1 && x <= n && y >= 1 && y <= n; } void bfs1(){ queue<pii> q; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(g[i][j] == 'H') d1[i][j] = 0, q.push(mp(i, j)); else d1[i][j] = inf; while(!q.empty()){ pii u = q.front(); q.pop(); for(int k = 0; k < 4; k++){ int x = u.fi + mv[k][0]; int y = u.se + mv[k][1]; if(valid(x, y) && g[x][y] != 'T' && g[x][y] != 'D' && d1[x][y] == inf){ d1[x][y] = d1[u.fi][u.se] + 1; q.push(mp(x, y)); } } } } bool check(int t){ queue<pii> q; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) d2[i][j] = inf; if(t < d1[mx][my]) d2[mx][my] = 0, q.push(mp(mx, my)); while(!q.empty()){ pii u = q.front(); q.pop(); for(int k = 0; k < 4; k++){ int x = u.fi + mv[k][0]; int y = u.se + mv[k][1]; if(valid(x, y) && g[x][y] != 'T' && d2[x][y] == inf && (t + (d2[u.fi][u.se] + 1) / s < d1[x][y])){ d2[x][y] = d2[u.fi][u.se] + 1; q.push(mp(x, y)); } } } return d2[dx][dy] != inf; } int main(){ // input scanf("%d %d", &n, &s); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++){ scanf(" %c", &g[i][j]); if(g[i][j] == 'M') mx = i, my = j; if(g[i][j] == 'D') dx = i, dy = j; } // prework(bfs) bfs1(); // binary search int l = -1, r = n * n, mid; while(l < r){ mid = (l + r + 1) / 2; if(check(mid)) l = mid; else r = mid - 1; } printf("%d\n", l); }

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

mecho.cpp: In function 'int main()':
mecho.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |  scanf("%d %d", &n, &s);
      |  ~~~~~^~~~~~~~~~~~~~~~~
mecho.cpp:69:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |    scanf(" %c", &g[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...