Submission #1326537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326537		hectormedrano	Mecho (IOI09_mecho)	C++20	100 / 100	755 ms	47184 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<vector<ll>> v;
ll N, S, ini, fin;

bool solve(ll T, deque<ll> bfs, vector<bool> vis, vector<char> ori){
    bfs.push_front(-1);
    vis[ini] = true;
    vector<ll> q1, q2;
    q1.push_back(ini);
    while(bfs.size() != 0){
        ll x = bfs.front();
        bfs.pop_front();
        if(x == -1 and T != 0){
            T--;
            bfs.push_back(-1);
            continue;
        }
        if(x == -1){
            for(ll i=0;i<S;i++){
                while(q1.size() != 0){
                    ll y = q1.back();
                    q1.pop_back();
                    if(ori[y] == 'H'){continue;}
                    for(ll z : v[y]){
                        if(z == fin){return true;}
                        if(vis[z]){continue;}
                        vis[z] = true;
                        ori[z] = 'M';
                        //cout<<"Casilla "<<z/N<<" "<<z%N<<" pasa a tener origen M"<<endl;
                        q2.push_back(z);
                    }
                }
                swap(q1, q2);
            }
            if(q1.size() != 0){bfs.push_back(-1);}
            continue;
        }
        for(ll y : v[x]){
            if(ori[y] == 'D'){continue;}
            if(ori[y] == 'M'){
                ori[y] = 'H';
                //cout<<"Casilla "<<y/N<<" "<<y%N<<" pasa a tener origen H"<<endl;
            }
            if(vis[y]){continue;}
            vis[y] = true;
            ori[y] = 'H';
            //cout<<"Casilla "<<y/N<<" "<<y%N<<" pasa a tener origen H"<<endl;
            bfs.push_back(y);
        }
    }
    return false;
}

int main() {
	cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cin>>N>>S;
    v.resize(N*N);
    vector<char> c(N*N);
    deque<ll> d;
    vector<bool> fij(N*N, false);
    for(ll i=0;i<N;i++){
        for(ll j=0;j<N;j++){
            cin>>c[N*i+j];
            if(c[N*i+j] == 'H'){
                d.push_back(N*i+j);
                fij[N*i+j] = true;
            }
            if(c[N*i+j] == 'M'){ini = N*i+j;}
            if(c[N*i+j] == 'D'){
                fin = N*i+j;
            }
        }
    }
    for(ll i=0;i<N;i++){
        for(ll j=0;j<N;j++){
            if(i > 0 and c[N*(i-1)+j] != 'T'){
                v[N*i+j].push_back(N*(i-1)+j);
            }
            if(i < N-1 and c[N*(i+1)+j] != 'T'){
                v[N*i+j].push_back(N*(i+1)+j);
            }
            if(j > 0 and c[N*i+(j-1)] != 'T'){
                v[N*i+j].push_back(N*i+(j-1));
            }
            if(j < N-1 and c[N*i+(j+1)] != 'T'){
                v[N*i+j].push_back(N*i+(j+1));
            }
        }
    }
    /*if(solve(1, d, fij, c)){cout<<"meow";}
    else{cout<<"wof";}*/
    if(!(solve(0, d, fij, c))){cout<<-1; return 0;}
    ll l = 0;
    ll r = N*N;
    while(r != l+1){
        ll m = (l+r)/2;
        if(solve(m, d, fij, c)){l = m;}
        else{r = m;}
        //cout<<l<<" "<<r<<endl;
    }
    cout<<l;
}

• Subtask 1: 100 / 100