# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
500026 | Nartifact | Mecho (IOI09_mecho) | C++14 | 160 ms | 7904 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define forinc(i,a,b) for(int i=a;i<=b;++i)
#define fordec(i,a,b) for(int i=a;i>=b;--i)
#define pb push_back
#define eb emplace_back
#define pii pair <int,int>
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int N = 888, inf = 1e15;
const int H[] = {1, 0, -1, 0};
const int C[] = {0, 1, 0, -1};
int n, s, cti = inf;
char a[N][N];
int t[N][N];
bool cx[N][N];
pii sta, fin;
bool valid (const int& x, const int& y)
{
return x && y && x <= n && y <= n
&& a[x][y] != 'T';
}
struct adt {int x, y, step;};
bool ok (const int& tg)
{
queue <adt> q;
memset(cx, 0, sizeof cx);
q.push({sta.fi, sta.se, 0});
cx[sta.fi][sta.se] = 1;
while(q.size()) {
auto tmp = q.front(); q.pop();
if(tmp.x == fin.fi && tmp.y == fin.se) return 1;
forinc(i,0,3) {
int nh = tmp.x + H[i];
int nc = tmp.y + C[i];
if(valid(nh, nc) && !cx[nh][nc] && (tmp.step + 1) / s <= t[nh][nc] - tg) {
q.push({nh, nc, tmp.step + 1});
cx[nh][nc] = 1;
}
}
}
return 0;
}
void solve ()
{
queue <pii> q;
forinc(i,1,n) forinc(j,1,n) {
t[i][j] = inf;
if(a[i][j] == 'H') {
q.push({i, j});
t[i][j] = 0;
}
else if(a[i][j] == 'M') sta = {i, j};
else if(a[i][j] == 'D') fin = {i, j};
}
// bfs bee
while(q.size()) {
auto x = q.front(); q.pop();
forinc(i,0,3) {
int nh = x.fi + H[i];
int nc = x.se + C[i];
if(valid(nh, nc) && t[nh][nc] > t[x.fi][x.se] + 1) {
t[nh][nc] = t[x.fi][x.se] + 1;
q.push({nh, nc});
}
}
}
// binary search
int l = 1, r = n * n * n, ans = -1;
while(l <= r) {
int mid = l + r >> 1;
if(ok(mid)) {
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
cout << ans;
}
void read ()
{
cin >> n >> s;
forinc(i,1,n) forinc(j,1,n)
cin >> a[i][j];
solve();
}
main ()
{
#define task "ioi09_mecho"
cin.tie(0) -> sync_with_stdio(0);
if(fopen (task ".inp", "r")) {
freopen (task ".inp", "r", stdin);
freopen (task ".out", "w", stdout);
}
read();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |