oj.uz

Submission #1050681

# Submission time Handle Problem Language Result Execution time Memory
1050681 2024-08-09T12:31:17 Z kvintsekstakord Mecho (IOI09_mecho) C++17
6 / 100
 88 ms 65536 KB 
#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));
            }
        }
    }
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            if(btime[i][j]==1e9){
                //cout << "x "; continue;
            };
            btime[i][j]*=S;
            //cout << btime[i][j] << " ";
        }//cout << endl;
    }
    int lo = 0;
    int hig = 1000000;
    lo--;
    while(lo<hig){
        int mid = lo+(hig-lo+1)/2;

        queue<src> bfs2;

        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;
            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<=btime[nx][ny]){
                    bfs2.push(src(nx, ny, step+1));
                }
            }
        }

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

    return 0;
}

Compilation message

mecho.cpp: In function 'int32_t main()':
mecho.cpp:84:26: warning: 'hj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |             if(x==hi && y==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;
      |             ^~
mecho.cpp:84:17: warning: 'hi' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |             if(x==hi && y==hj){
      |                ~^~~~

Subtask #1
6.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Incorrect 0 ms 4444 KB Output isn't correct
4 Incorrect 0 ms 4444 KB Output isn't correct
5 Correct 0 ms 4512 KB Output is correct
6 Correct 8 ms 7004 KB Output is correct
7 Runtime error 78 ms 65536 KB Execution killed with signal 9
8 Incorrect 1 ms 4444 KB Output isn't correct
9 Runtime error 53 ms 65536 KB Execution killed with signal 9
10 Correct 62 ms 54168 KB Output is correct
11 Correct 10 ms 12360 KB Output is correct
12 Incorrect 0 ms 4444 KB Output isn't correct
13 Runtime error 50 ms 65536 KB Execution killed with signal 9
14 Runtime error 52 ms 65536 KB Execution killed with signal 9
15 Incorrect 1 ms 4444 KB Output isn't correct
16 Runtime error 63 ms 65536 KB Execution killed with signal 9
17 Incorrect 0 ms 4444 KB Output isn't correct
18 Runtime error 61 ms 65536 KB Execution killed with signal 9
19 Incorrect 1 ms 4444 KB Output isn't correct
20 Runtime error 63 ms 65536 KB Execution killed with signal 9
21 Incorrect 1 ms 4444 KB Output isn't correct
22 Runtime error 65 ms 65536 KB Execution killed with signal 9
23 Incorrect 1 ms 4444 KB Output isn't correct
24 Runtime error 60 ms 65536 KB Execution killed with signal 9
25 Incorrect 1 ms 4444 KB Output isn't correct
26 Runtime error 63 ms 65536 KB Execution killed with signal 9
27 Incorrect 1 ms 4440 KB Output isn't correct
28 Runtime error 60 ms 65536 KB Execution killed with signal 9
29 Incorrect 1 ms 4444 KB Output isn't correct
30 Runtime error 60 ms 65536 KB Execution killed with signal 9
31 Incorrect 1 ms 6492 KB Output isn't correct
32 Runtime error 59 ms 65536 KB Execution killed with signal 9
33 Incorrect 5 ms 8540 KB Output isn't correct
34 Runtime error 59 ms 65536 KB Execution killed with signal 9
35 Runtime error 59 ms 65536 KB Execution killed with signal 9
36 Incorrect 6 ms 8796 KB Output isn't correct
37 Runtime error 62 ms 65536 KB Execution killed with signal 9
38 Runtime error 61 ms 65536 KB Execution killed with signal 9
39 Incorrect 7 ms 8796 KB Output isn't correct
40 Runtime error 66 ms 65536 KB Execution killed with signal 9
41 Runtime error 62 ms 65536 KB Execution killed with signal 9
42 Incorrect 8 ms 8796 KB Output isn't correct
43 Runtime error 64 ms 65536 KB Execution killed with signal 9
44 Runtime error 62 ms 65536 KB Execution killed with signal 9
45 Incorrect 10 ms 8796 KB Output isn't correct
46 Runtime error 64 ms 65536 KB Execution killed with signal 9
47 Runtime error 64 ms 65536 KB Execution killed with signal 9
48 Incorrect 12 ms 10844 KB Output isn't correct
49 Runtime error 65 ms 65536 KB Execution killed with signal 9
50 Runtime error 66 ms 65536 KB Execution killed with signal 9
51 Incorrect 14 ms 11100 KB Output isn't correct
52 Runtime error 68 ms 65536 KB Execution killed with signal 9
53 Runtime error 68 ms 65536 KB Execution killed with signal 9
54 Incorrect 16 ms 11100 KB Output isn't correct
55 Runtime error 69 ms 65536 KB Execution killed with signal 9
56 Runtime error 75 ms 65536 KB Execution killed with signal 9
57 Incorrect 18 ms 11196 KB Output isn't correct
58 Runtime error 71 ms 65536 KB Execution killed with signal 9
59 Runtime error 70 ms 65536 KB Execution killed with signal 9
60 Incorrect 21 ms 11096 KB Output isn't correct
61 Runtime error 75 ms 65536 KB Execution killed with signal 9
62 Runtime error 76 ms 65536 KB Execution killed with signal 9
63 Runtime error 81 ms 65536 KB Execution killed with signal 9
64 Runtime error 81 ms 65536 KB Execution killed with signal 9
65 Runtime error 81 ms 65536 KB Execution killed with signal 9
66 Runtime error 80 ms 65536 KB Execution killed with signal 9
67 Runtime error 87 ms 65536 KB Execution killed with signal 9
68 Runtime error 80 ms 65536 KB Execution killed with signal 9
69 Runtime error 81 ms 65536 KB Execution killed with signal 9
70 Runtime error 82 ms 65536 KB Execution killed with signal 9
71 Runtime error 81 ms 65536 KB Execution killed with signal 9
72 Runtime error 88 ms 65536 KB Execution killed with signal 9
73 Runtime error 75 ms 65536 KB Execution killed with signal 9
74 Runtime error 68 ms 65536 KB Execution killed with signal 9
75 Runtime error 67 ms 65536 KB Execution killed with signal 9
76 Runtime error 68 ms 65536 KB Execution killed with signal 9
77 Runtime error 68 ms 65536 KB Execution killed with signal 9
78 Runtime error 68 ms 65536 KB Execution killed with signal 9
79 Runtime error 71 ms 65536 KB Execution killed with signal 9
80 Runtime error 70 ms 65536 KB Execution killed with signal 9
81 Runtime error 75 ms 65536 KB Execution killed with signal 9
82 Runtime error 69 ms 65536 KB Execution killed with signal 9
83 Runtime error 68 ms 65536 KB Execution killed with signal 9
84 Runtime error 69 ms 65536 KB Execution killed with signal 9
85 Runtime error 68 ms 65536 KB Execution killed with signal 9
86 Runtime error 71 ms 65536 KB Execution killed with signal 9
87 Runtime error 68 ms 65536 KB Execution killed with signal 9
88 Runtime error 67 ms 65536 KB Execution killed with signal 9
89 Runtime error 68 ms 65536 KB Execution killed with signal 9
90 Runtime error 69 ms 65536 KB Execution killed with signal 9
91 Runtime error 71 ms 65536 KB Execution killed with signal 9
92 Runtime error 68 ms 65536 KB Execution killed with signal 9