Submission #1118604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118604		ojoConmigo	Mecho (IOI09_mecho)	C++17	43 / 100	208 ms	6212 KiB

mecho

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define D(x) cout << #x << ':' << ' ' << x << endl;
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)

using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

typedef long long ll;
typedef long double ld;

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

enum {
    T=-4,G,M,D,H=0
};

const int MX = 801;
const int sx[] = {0,1,-1,0};
const int sy[] = {1,0,0,-1};
int n,s;
pii ini, fin;
int bee[MX][MX];
//int steps[MX][MX];
int max_min = 0;

bool valid(int x){
    return 0 <= x && x < n;
}

bool valid(int x, int y){
    return valid(x) && valid(y);
}

void bfs(vector<pii> & hives){
    queue<pii> q;
    for(auto h : hives) q.push(h);
    while(!q.empty()){
        auto [x,y] = q.front();
        q.pop();
        for(int i=0;i<4;++i){
            int nx = x+sx[i];
            int ny = y+sy[i];
            if(valid(nx,ny) && bee[nx][ny] == G){
                bee[nx][ny] = bee[x][y]+1;
                max_min = max(max_min,bee[nx][ny]);
                q.push({nx,ny});
            }
        }
    }
}
/*
void step(){
    queue<pii> q;
    q.push(ini);
    steps[ini.first][ini.second] = -1;
    while(!q.empty()){
        auto [x,y] = q.front();
        q.pop();
        for(int i=0;i<4;++i){
            int nx = x+sx[i];
            int ny = y+sy[i];
            if(valid(nx,ny) && steps[nx][ny] == -1 && (bee[nx][ny] > 0 || bee[nx][ny] == D)){
                steps[nx][ny] = steps[x][y]+1;
                q.push({nx,ny});
            }
        }
    }
}

bool mecho(int ini_minute){
    vector<vector<bool>> vis(n,vector<bool>(n,false));
    queue<pii> q;
    q.push(ini);
    vis[ini.first][ini.second] = true;
    while(!q.empty()){
        auto [x,y] = q.front();
        q.pop();
        for(int i=0;i<4;++i){
            int nx = x+sx[i];
            int ny = y+sy[i];
            if(valid(nx,ny) && !vis[nx][ny]){
                vis[nx][ny] = true;
                if(bee[nx][ny] == D)return true;
                if(bee[nx][ny] > ini_minute+((steps[nx][ny])/s))
                    q.push({nx,ny});
            }
        }
    }
    return false;
}
*/

bool mecho(int ini_minute){
    //vector<vector<bool>> vis(n,vector<bool>(n,false));
    vvi steps(n,vi(n,-1));
    queue<pii> q;
    q.push(ini);
    //vis[ini.first][ini.second] = true;
    steps[ini.first][ini.second] = 0;
    while(!q.empty()){
        auto [x,y] = q.front();
        q.pop();
        for(int i=0;i<4;++i){
            int nx = x+sx[i];
            int ny = y+sy[i];
            if(valid(nx,ny) && steps[nx][ny] == -1){
                if(bee[nx][ny] == D)return true;
                if(bee[nx][ny] > ini_minute+((steps[x][y])/s)){
                    //D(nx)D(ny)
                    steps[nx][ny] = steps[x][y]+1;
                    q.push({nx,ny});
                }
                    
            }
        }
    }
    return false;
}

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

    cin >> n >> s;
    vector<pii> hives;
    for(int i = 0; i < n; ++i){
        for(int j=0; j<n; ++j){
            char c; cin >> c;
            switch (c)
            {
            case 'T':
                bee[i][j] = T;    
                break;
            case 'M':
                ini = {i,j};
                bee[i][j] = M;  
                break;
            case 'D':
                fin = {i,j};
                bee[i][j] = D;
                break;
            case 'G':
                bee[i][j] = G;  
                break;
            case 'H':
                hives.emplace_back(i,j);
                bee[i][j] = H;
                break;
            }
            //steps[i][j] = -1;
        }
    }

    bfs(hives);
    //step();
    /*cout << "bees\n";
    for(int i = 0; i < n; ++i){
        for(int j=0;j<n;++j){
            cout << bee[i][j] << ' ';
        }
        cout << endl;
    }
    cout << "steps\n";
    for(int i = 0; i < n; ++i){
        for(int j=0;j<n;++j){
            cout << steps[i][j] << ' ';
        }
        cout << endl;
    }*/
    int lo = 0,hi = max_min,ans=-1,mid;
    while(lo <= hi){
        mid = (lo+hi)/2;
        if(mecho(mid)){
            ans = mid;
            lo = mid+1;
        }else{
            hi = mid-1;
        }
    }

    cout << ans << endl;

    return 0;
}

• Subtask 1: 43 / 100