제출 #687022

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
687022		ar88lo	Mecho (IOI09_mecho)	C++14	17 / 100	340 ms	14928 KiB

mecho

#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'){
        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'){
        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'){
        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'){
        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;
        }
    }
    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;
        }
    }
    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);

    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;
}

• Subtask 1: 17 / 100