Submission #596093

#	Time	Username	Problem	Language	Result	Execution time	Memory
596093		mosiashvililuka	Mecho (IOI09_mecho)	C++14	100 / 100	242 ms	12656 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
const int N=2000009;
int a,c,d,e,i,j,ii,jj,zx,xc,S,B[809][809],lef,rig,mid,f[809][809],Mi,Mj,X[809][809],dis[809][809],Di,Dj;
bool bo[809][809];
string s;
char ch[809][809];
deque <pair <int, int> > de;
void chk(int q, int w){
    if(q<1||q>a||w<1||w>a) return;
    if(f[q][w]==0) return;
    if(B[q][w]>B[i][j]+1){
        B[q][w]=B[i][j]+1;
        de.push_back({q,w});
    }
}
void CHK(int q, int w){
    if(q<1||q>a||w<1||w>a) return;
    if(f[q][w]==0) return;
    if(bo[q][w]==1) return;
    if(dis[i][j]+1>X[q][w]) return;
    bo[q][w]=1;
    dis[q][w]=dis[i][j]+1;
    de.push_back({q,w});
}
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a>>S;
    for(i=1; i<=a; i++){
        cin>>s;
        for(j=1; j<=a; j++){
            ch[i][j]=s[j-1];
        }
    }
    for(i=0; i<=a+1; i++){
        for(j=0; j<=a+1; j++){
            B[i][j]=N;
        }
    }
    for(i=1; i<=a; i++){
        for(j=1; j<=a; j++){
            if(ch[i][j]=='H'){
                de.push_back({i,j});
                B[i][j]=0;
            }
            if(ch[i][j]=='T'||ch[i][j]=='D'){
                f[i][j]=0;
            }else{
                f[i][j]=1;
            }
            if(ch[i][j]=='M'){
                Mi=i;Mj=j;
            }
            if(ch[i][j]=='D'){
                Di=i;Dj=j;
            }
        }
    }
    while(de.size()){
        i=de.front().first;j=de.front().second;
        de.pop_front();
        chk(i+1,j);chk(i-1,j);chk(i,j+1);chk(i,j-1);
    }
    /*for(i=1; i<=a; i++){
        for(j=1; j<=a; j++){
            cout<<B[i][j]<<" ";
        }
        cout<<"\n";
    }*/
    lef=-1;rig=a*a+2;
    while(1){
        if(lef+1>=rig) break;
        mid=(lef+rig)/2;
        if(B[Mi][Mj]<=mid){
            rig=mid;
            continue;
        }
        for(i=1; i<=a; i++){
            for(j=1; j<=a; j++){
                if(ch[i][j]=='T'||ch[i][j]=='H'){
                    f[i][j]=0;
                }else{
                    f[i][j]=1;
                }
                bo[i][j]=0;
                if(B[i][j]<=mid){
                    X[i][j]=-1;
                }else{
                    zx=B[i][j]-mid;
                    X[i][j]=zx*S-1;
                }
            }
        }
        while(de.size()) de.pop_back();
        de.push_back({Mi,Mj});bo[Mi][Mj]=1;dis[Mi][Mj]=0;
        while(de.size()){
            i=de.front().first;j=de.front().second;
            de.pop_front();
            CHK(i+1,j);CHK(i-1,j);CHK(i,j+1);CHK(i,j-1);
        }
        if(bo[Di][Dj]==1){
            lef=mid;
        }else{
            rig=mid;
        }
    }
    cout<<lef;
    return 0;
}

• Subtask 1: 100 / 100