Submission #411435

#	Time	Username	Problem	Language	Result	Execution time	Memory
411435		pliam	Mecho (IOI09_mecho)	C++14	100 / 100	299 ms	8136 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define MAXN 805
#define INF (int)1e9
typedef pair<int,int> pii;

int N,S;
char grid[MAXN][MAXN];
int dist_bees[MAXN][MAXN];
int dist_mecho[MAXN][MAXN];
pii mecho,home;

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

bool inbounds(int x,int y){
    return 1<=x&&x<=N&&1<=y&&y<=N;
}

bool check(int k){//k<=dist_bees[mecho.first][mecho.second]-1
    queue<pii> q;
    bool used[MAXN][MAXN];
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            used[i][j]=false;
            dist_mecho[i][j]=INF;
        }
    }
    used[mecho.first][mecho.second]=true;
    dist_mecho[mecho.first][mecho.second]=0;
    q.push(mecho);
    while(!q.empty()){
        pii p=q.front();
        q.pop();
        int x=p.first;
        int y=p.second;
        for(auto d:deltas){
            int x_=x+d.first;
            int y_=y+d.second;
            int steps=dist_mecho[x][y]+1;
            if(make_pair(x_,y_)==home) return true;
            if(inbounds(x_,y_)&&grid[x_][y_]=='G'&&!used[x_][y_]&&(steps/S+k<dist_bees[x_][y_])){
                used[x_][y_]=true;
                dist_mecho[x_][y_]=steps;
                q.push({x_,y_});
            }
        }
    }
    return false;
}

int main(){
    scanf("%d%d",&N,&S);
    queue<pii> q;
    bool used[MAXN][MAXN];
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            used[i][j]=false;
            dist_bees[i][j]=INF;
            scanf(" %c",&grid[i][j]);
            if(grid[i][j]=='M') mecho={i,j};
            else if(grid[i][j]=='D') home={i,j};
            else if(grid[i][j]=='H'){
                q.push({i,j});//hive
                dist_bees[i][j]=0;
                used[i][j]=true;
            }
        }
    }
    while(!q.empty()){
        pii p=q.front();
        q.pop();
        int x=p.first;
        int y=p.second;
        for(auto d:deltas){
            int x_=x+d.first;
            int y_=y+d.second;
            if(inbounds(x_,y_)&&(grid[x_][y_]=='G'||grid[x_][y_]=='M')&&!used[x_][y_]){
                used[x_][y_]=true;
                dist_bees[x_][y_]=dist_bees[x][y]+1;
                q.push({x_,y_});
            }
        }
    }
    int ans=0;
    int max_ans=dist_bees[mecho.first][mecho.second]-1;
    for(int b=max_ans;b>0;b/=2){
        while(ans+b<=max_ans&&check(ans+b)) ans+=b;
    }
    printf("%d\n",check(ans)?ans:-1);
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     scanf("%d%d",&N,&S);
      |     ~~~~~^~~~~~~~~~~~~~
mecho.cpp:59:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |             scanf(" %c",&grid[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100