Submission #1050708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050708		kvintsekstakord	Mecho (IOI09_mecho)	C++17	84 / 100	97 ms	7516 KiB

mecho

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

int N, S;
char forest[810][810];
int btime[810][810];
bool visited[810][810];

int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};

struct src{
    int x, y;
    int step;
    src(int x, int y, int step) : x(x), y(y), step(step){};
};

int32_t main()
{
    cin >> N >> S;
    queue<src> bfs;
    int si, sj;
    int hi, hj;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            cin >> forest[i][j];
            btime[i][j]=1e9;

            if(forest[i][j]=='H'){
                bfs.push(src(i, j, 0));
                btime[i][j]=0;
            }
            if(forest[i][j]=='M'){
                si = i;
                sj = j;
            }
            if(forest[i][j]=='D'){
                hi=i; hj=j;
            }

        }
    }

    while(!bfs.empty()){
        int x = bfs.front().x;
        int y = bfs.front().y;
        int step = bfs.front().step;
        bfs.pop();
        for(int i = 0; i < 4; i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(nx<1 || nx>N || ny<1 || ny>N) continue;
            if(forest[nx][ny]=='T' || forest[nx][ny]=='D') continue;
            if(step+1<btime[nx][ny]){
                btime[nx][ny]=(step+1);
                bfs.push(src(nx, ny, step+1));
            }
        }
    }
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            btime[i][j]*=S;
        }
    }
    int lo = 0;
    int hig = 10000000;
    lo--;
    while(lo<hig){
        int mid = lo+(hig-lo+1)/2;

        queue<src> bfs2;
        memset(visited, false, sizeof(visited));
        visited[si][sj]=true;
        bfs2.push({si, sj, mid*S});
        bool possible = false;
        while(!bfs2.empty()){
            int x = bfs2.front().x;
            int y = bfs2.front().y;
            int step = bfs2.front().step;

            bfs2.pop();
            for(int i = 0; i < 4; i++){
                int nx = x+dx[i];
                int ny = y+dy[i];
                if(nx<1 || nx>N || ny<1 || ny>N) continue;
                if(forest[nx][ny]=='T') continue;
                if(forest[nx][ny]=='D'){
                    possible = true;
                    break;
                }
                if(visited[nx][ny]) continue;
                if( step+1<btime[nx][ny]){
                    visited[nx][ny]=true;
                    bfs2.push(src(nx, ny, step+1));
                }
            }
            if(possible) break;
        }

        if(possible){
            lo = mid;
        }else{
            hig = mid-1;
        }
    }
    cout << lo;

    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int32_t main()':
mecho.cpp:24:9: warning: variable 'hi' set but not used [-Wunused-but-set-variable]
   24 |     int hi, hj;
      |         ^~
mecho.cpp:24:13: warning: variable 'hj' set but not used [-Wunused-but-set-variable]
   24 |     int hi, hj;
      |             ^~
mecho.cpp:16:56: warning: 'si' may be used uninitialized in this function [-Wmaybe-uninitialized]
   16 |     src(int x, int y, int step) : x(x), y(y), step(step){};
      |                                                        ^
mecho.cpp:23:9: note: 'si' was declared here
   23 |     int si, sj;
      |         ^~
mecho.cpp:16:56: warning: 'sj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   16 |     src(int x, int y, int step) : x(x), y(y), step(step){};
      |                                                        ^
mecho.cpp:23:13: note: 'sj' was declared here
   23 |     int si, sj;
      |             ^~

• Subtask 1: 84 / 100