# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
687384 | ar88lo | Mecho (IOI09_mecho) | C++14 | 910 ms | 14924 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
#define double (long double)
using namespace std;
struct node{
int x; int y;
};
const int max_n = 1000, INF = 1e8;
int n,s;
string a[max_n];
bool ch[max_n][max_n];
int dis[max_n][max_n][2];
queue<node> src;
node st,dt;
bool isin(node u){
return (u.x >= 0 && u.y >= 0 && u.x < n && u.y < n);
}
bool safe(node u, int h){
return (dis[u.x][u.y][0] - h > ceil(double(dis[u.x][u.y][1])/double(s)));
}
void relax1(node v, bool ty){
node u,d,l,r;
u = d = l = r = v;
u.y++; d.y--; l.x--; r.x++;
if(isin(u) && ch[u.x][u.y] == 0 && a[u.x][u.y] != 'T' && a[u.x][u.y] != 'D'){
ch[u.x][u.y] = 1;
dis[u.x][u.y][ty] = dis[v.x][v.y][ty] + 1;
src.push(u);
}
if(isin(d) && ch[d.x][d.y] == 0 && a[d.x][d.y] != 'T' && a[d.x][d.y] != 'D'){
ch[d.x][d.y] = 1;
dis[d.x][d.y][ty] = dis[v.x][v.y][ty] + 1;
src.push(d);
}
if(isin(l) && ch[l.x][l.y] == 0 && a[l.x][l.y] != 'T' && a[l.x][l.y] != 'D'){
ch[l.x][l.y] = 1;
dis[l.x][l.y][ty] = dis[v.x][v.y][ty] + 1;
src.push(l);
}
if(isin(r) && ch[r.x][r.y] == 0 && a[r.x][r.y] != 'T' && a[r.x][r.y] != 'D'){
ch[r.x][r.y] = 1;
dis[r.x][r.y][ty] = dis[v.x][v.y][ty] + 1;
src.push(r);
}
}
void relax2(node v, int h){
node u,d,l,r;
u = d = l = r = v;
u.y++; d.y--; l.x--; r.x++;
if(isin(u) && safe(u, h) && ch[u.x][u.y] == 0 && a[u.x][u.y] != 'T'){
ch[u.x][u.y] = 1;
src.push(u);
}
if(isin(d) && safe(d, h) && ch[d.x][d.y] == 0 && a[d.x][d.y] != 'T'){
ch[d.x][d.y] = 1;
src.push(d);
}
if(isin(l) && safe(l, h) && ch[l.x][l.y] == 0 && a[l.x][l.y] != 'T'){
ch[l.x][l.y] = 1;
src.push(l);
}
if(isin(r) && safe(r, h) && ch[r.x][r.y] == 0 && a[r.x][r.y] != 'T'){
src.push(r);
ch[r.x][r.y] = 1;
}
}
bool check(int h){
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++){
ch[i][j] = 0;
}
}
ch[st.x][st.y] = 1;
src.push(st);
while(!src.empty()){
node u = src.front();
src.pop();
relax2(u, h);
}
return ch[dt.x][dt.y];
}
void bfs(bool ty){
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++){
ch[i][j] = 0;
}
}
queue<node>temp = src;
while(!temp.empty()){
ch[temp.front().x][temp.front().y] = 1;
temp.pop();
}
while(!src.empty()){
node u = src.front();
src.pop();
relax1(u, ty);
}
}
int32_t main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
node temp;
cin>>n>>s;
for(int i = 0; i < n; i++){
cin>>a[i];
for(int j = 0; j < n; j++){
if(a[i][j] == 'M'){
st.x = i; st.y = j;
}
if(a[i][j] == 'D'){
dt.x = i; dt.y = j;
}
if(a[i][j] == 'H'){
temp.x = i; temp.y = j;
src.push(temp);
}
}
}
bfs(0);
src.push(st);
bfs(1);
dis[dt.x][dt.y][0] = INF * INF;
int ans = -1;
for(int k = INF; k > 0; k /= 2){
while(ans + k < INF && check(ans + k)) ans += k;
}
cout<<ans<<'\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |