Submission #1230313

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230313		lukasuliashvili	Mecho (IOI09_mecho)	C++20	73 / 100	344 ms	62120 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fs first 
#define sc second 
#define pb push_back
const int N=805;
char a[N][N],g[N*N];
vector<int> v[N*N];
int fix[N*N],t[N*N],n,s,fix2[N*N],t2[N*N],st,en;
int check(int mid ){
    for(int i=1; i<=n*n; i++){
        t2[i]=1e9;
        fix[i]=0;
    }
    deque<int> deq;
        deq.pb(st);
        fix[st]=1;
        t2[st]=mid;
    while(!deq.empty()){
        int to=deq.front();
        deq.pop_front();
        for(int i=0; i<v[to].size(); i++){
            int to1=v[to][i];
            if(g[to1]=='D' and t[to1]>=min(t2[to1],t2[to]+1)){
                return 1;
            }
            if(fix[to1]==1 or t[to1]<=min(t2[to1],t2[to]+1)){
                continue;
            }
            t2[to1]=min(t2[to1],t2[to]+1);
            deq.pb(to1);
            fix[to1]=1;
        }
    }
    // for(int i=1; i<=n; i++){
    //     for(int j=1; j<=n; j++){
    //         cout<<t2[(i-1)*n+j]<<" ";
    //     }
    //     cout<<endl;
    // }
    if(t2[en]!=1e9){
        return 1;
    }
    else{
        return -1;
    }
    
}
void bfs (){
    deque<int> deq;
    for(int i=1; i<=n*n; i++){
        if(g[i]=='H'){
            deq.pb(i);
            fix[i]=1;
            t[i]=0;
        }
    }
    while(!deq.empty()){
        int to=deq.front();
        deq.pop_front();
        for(int i=0; i<v[to].size(); i++){
            int to1=v[to][i];
            if(fix[to1]==1){
                continue;
            }
            t[to1]=min(t[to1],t[to]+s);
            deq.pb(to1);
            fix[to1]=1;
        }
    }
}
signed main(){
    cin>>n>>s;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin>>a[i][j];
            g[(i-1)*n+j]=a[i][j];
        }
    }
    for(int i=1; i<=n*n; i++){
        t[i]=1e9;
        t2[i]=1e9;
        if(g[i]=='M'){
            st=i;
        }
        if(g[i]=='D'){
            en=i;
        }
    }
    for(int i=1; i<=n*n; i++){
        if(g[i]=='T')continue;
        if(i+1>=1 and i+1<=n*n){
            if(g[i]!='T' and g[i+1]!='T' and i%n!=0){
                v[i].pb(i+1);
                v[i+1].pb(i);
            }
        }
        if(i+n<=n*n and i+n>=1 ){
            if(g[i+n]!='T' and g[i]!='T'){
                v[i].pb(i+n);
                v[i+n].pb(i);
            }
        }
    }
    bfs();
    if(check(0)==-1){
        cout<<-1<<endl;
        return 0;
    }
    int l=0;
    int r=n*n;
    int ans=0;
    // for(int i=1; i<=n; i++){
    //     for(int j=1; j<=n; j++){
    //         cout<<t[(i-1)*n+j]<<" ";
    //     }
    //     cout<<endl;
    // }
    
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid*s)!=-1){
            l=mid+1;
            ans=max(mid,ans);
        }
        else{
            r=mid-1;
        }
    }
    cout<<ans<<endl;




}

• Subtask 1: 73 / 100