Submission #1335605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1335605		ivalolre	Mecho (IOI09_mecho)	C++20	100 / 100	133 ms	4204 KiB

mecho

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

#define fore(i,a,b) for(int i=a;i<=b;i++)

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef pair<int,int> pii;

vector<pii> mov = {{0,1},{1,0},{0,-1},{-1,0}};

struct nodoCola{
    int y,x,t;
};

void abejitas(vector<string> &mapa, vvi &tiempo, int inc){
    int n = mapa.size();
    queue<nodoCola> cola;
    vvb visto(n,vb(n,false));

    fore(i,0,n-1){
        fore(j,0,n-1){
            if(mapa[i][j]=='H'){
                cola.push({i,j,0});
                visto[i][j]=true;
                tiempo[i][j]=0;
            }
        }
    }

    while(!cola.empty()){
        auto act = cola.front(); cola.pop();

        for(auto [dy,dx]:mov){
            int ny = act.y + dy;
            int nx = act.x + dx;

            if(ny<0||nx<0||ny>=n||nx>=n) continue;
            if(visto[ny][nx]) continue;
            if(mapa[ny][nx]!='G' && mapa[ny][nx]!='M') continue;

            visto[ny][nx]=true;
            tiempo[ny][nx]=act.t+inc;
            cola.push({ny,nx,act.t+inc});
        }
    }
}

int ey,ex;

bool osito(vector<string> &mapa, vvi &tiempo, int startTime){
    int n = mapa.size();
    queue<nodoCola> cola;
    vvb visto(n,vb(n,false));

    cola.push({ey,ex,startTime});
    visto[ey][ex]=true;

    while(!cola.empty()){
        auto act = cola.front(); cola.pop();

        for(auto [dy,dx]:mov){
            int ny = act.y + dy;
            int nx = act.x + dx;

            if(ny<0||nx<0||ny>=n||nx>=n) continue;
            if(visto[ny][nx]) continue;
            if(mapa[ny][nx]!='G' && mapa[ny][nx]!='D') continue;

            if(mapa[ny][nx]=='D') return true;

            if(tiempo[ny][nx] <= act.t+1) continue;

            visto[ny][nx]=true;
            cola.push({ny,nx,act.t+1});
        }
    }

    return false;
}

int solve(){
    int n,s;
    cin>>n>>s;

    vector<string> mapa(n);
    fore(i,0,n-1) cin>>mapa[i];

    const int INF = 1e9;
    vvi tiempo(n,vi(n,INF));

    abejitas(mapa,tiempo,s);

    fore(i,0,n-1){
        fore(j,0,n-1){
            if(mapa[i][j]=='M'){
                ey=i;
                ex=j;
            }
        }
    }

    int l=0;
    int r=tiempo[ey][ex]/s;
    int ans=-1;

    while(l<=r){
        int mid=(l+r)/2;

        if(mid*s < tiempo[ey][ex] && osito(mapa,tiempo,mid*s)){
            ans=mid;
            l=mid+1;
        }else{
            r=mid-1;
        }
    }

    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cout<<solve()<<"\n";
}

• Subtask 1: 100 / 100