Submission #688151

#	Time	Username	Problem	Language	Result	Execution time	Memory
688151		ar88lo	Mecho (IOI09_mecho)	C++14	84 / 100	187 ms	15564 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 > dis[u.x][u.y][1]/s);
}
void f(node v, node u){
    if(isin(v) && !ch[v.x][v.y] && a[v.x][v.y] != 'T' && a[v.x][v.y] != 'D'){
        dis[v.x][v.y][0] = dis[u.x][u.y][0] + 1;
        ch[v.x][v.y] = 1;
        src.push(v);
    }
}
void g(node v, node u, int h){
    if(isin(v) && ch[v.x][v.y] == 0 && a[v.x][v.y] != 'T'){
        dis[v.x][v.y][1] = dis[u.x][u.y][1] + 1;
        if(safe(v, h)){
        ch[v.x][v.y] = 1;
        src.push(v);
        }
    }
}
void relax1(node v){
    
    node u,d,l,r;
    u = d = l = r = v;
    u.y++; d.y--; l.x--; r.x++;
    f(u, v); f(d, v); f(l, v); f(r, v);
}
void relax2(node v, int h){

    node u,d,l,r;
    u = d = l = r = v;
    u.y++; d.y--; l.x--; r.x++;
    g(u, v, h); g(d, v, h); g(l, v, h); g(r, v, h);
}
bool check(int h){

    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            ch[i][j] = 0;
            dis[i][j][1] = INF;
        }
    }
    ch[st.x][st.y] = 1;
    dis[st.x][st.y][1] = 0;
    src.push(st);
    while(!src.empty()){
        node u = src.front();
        src.pop();
        relax2(u, h);
    }
    return ch[dt.x][dt.y];
}
void bfs(){

    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);
    }
}
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();
    src.push(st);
    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;
}

• Subtask 1: 84 / 100