Submission #1049576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049576		kvintsekstakord	Mecho (IOI09_mecho)	C++17	15 / 100	125 ms	65536 KiB

mecho

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

int N, S;
char forest[1000][1000];
int btime[1000][1000];
int mtime[1000][1000];

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));
            }
        }
    }

    int lo = 0;
    int hig = 1000000;
    lo--;
    while(lo<hig){
        int mid = lo+(hig-lo+1)/2;

        queue<src> bfs2;
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j++){
                mtime[i][j]=1e9;
            }
        }
        bfs2.push({si, sj, mid*S});
        mtime[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;
            if(x==hi && y==hj){
                possible = true;
                break;
            }
            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' || forest[nx][ny]=='H') continue;
                if(step+1>mtime[nx][ny]) continue;
                int minute = (int)ceil((step+1)/(double)(S));
                if( minute<=btime[nx][ny]){
                    mtime[nx][ny]=step+1;
                    bfs2.push(src(nx, ny, step+1));
                }
            }
        }

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

    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int32_t main()':
mecho.cpp:80:26: warning: 'hj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |             if(x==hi && y==hj){
      |                         ~^~~~
mecho.cpp:80:17: warning: 'hi' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |             if(x==hi && y==hj){
      |                ~^~~~
mecho.cpp:74:22: warning: 'sj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |         mtime[si][sj]=mid*S;
      |         ~~~~~~~~~~~~~^~~~~~
mecho.cpp:74:22: warning: 'si' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 15 / 100