Submission #1230323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230323		lukasuliashvili	Mecho (IOI09_mecho)	C++20	65 / 100	329 ms	67128 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;
        fix2[i] = 0;
    }

    deque<int> deq;
    t2[st] = mid;
    deq.pb(st);

    while (!deq.empty()) {
        int to = deq.front();
        deq.pop_front();

        if (fix2[to]) continue;
        fix2[to] = 1;

        for (int to1 : v[to]) {
            if (g[to1] == 'T') continue;

            int arrive = t2[to] + 1;

            if (g[to1] == 'D') return 1; 
            if (arrive >= t[to1]) continue; 

            if (t2[to1] > arrive) {
                t2[to1] = arrive;
                deq.pb(to1);
            }
        }
    }

    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: 65 / 100