oj.uz

Submission #1050687

# Submission time Handle Problem Language Result Execution time Memory
1050687 2024-08-09T12:37:36 Z kvintsekstakord Mecho (IOI09_mecho) C++17
15 / 100
 132 ms 65536 KB 
#include <bits/stdc++.h>
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:83:26: warning: 'hj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   83 |             if(x==hi && y==hj){
      |                         ~^~~~
mecho.cpp:15:56: warning: 'si' may be used uninitialized in this function [-Wmaybe-uninitialized]
   15 |     src(int x, int y, int step) : x(x), y(y), step(step){};
      |                                                        ^
mecho.cpp:22:9: note: 'si' was declared here
   22 |     int si, sj;
      |         ^~
mecho.cpp:15:56: warning: 'sj' may be used uninitialized in this function [-Wmaybe-uninitialized]
   15 |     src(int x, int y, int step) : x(x), y(y), step(step){};
      |                                                        ^
mecho.cpp:22:13: note: 'sj' was declared here
   22 |     int si, sj;
      |             ^~
mecho.cpp:83:17: warning: 'hi' may be used uninitialized in this function [-Wmaybe-uninitialized]
   83 |             if(x==hi && y==hj){
      |                ~^~~~

Subtask #1
15.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4444 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Correct 0 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Incorrect 113 ms 36596 KB Output isn't correct
6 Runtime error 126 ms 65536 KB Execution killed with signal 9
7 Runtime error 89 ms 65536 KB Execution killed with signal 9
8 Correct 1 ms 4444 KB Output is correct
9 Runtime error 79 ms 65536 KB Execution killed with signal 9
10 Correct 19 ms 9308 KB Output is correct
11 Runtime error 80 ms 65536 KB Execution killed with signal 9
12 Incorrect 1 ms 4444 KB Output isn't correct
13 Runtime error 69 ms 65536 KB Execution killed with signal 9
14 Runtime error 74 ms 65536 KB Execution killed with signal 9
15 Correct 1 ms 4440 KB Output is correct
16 Runtime error 94 ms 65536 KB Execution killed with signal 9
17 Correct 1 ms 4444 KB Output is correct
18 Runtime error 100 ms 65536 KB Execution killed with signal 9
19 Correct 1 ms 4444 KB Output is correct
20 Runtime error 89 ms 65536 KB Execution killed with signal 9
21 Correct 1 ms 4444 KB Output is correct
22 Runtime error 91 ms 65536 KB Execution killed with signal 9
23 Correct 1 ms 4444 KB Output is correct
24 Runtime error 92 ms 65536 KB Execution killed with signal 9
25 Correct 1 ms 4444 KB Output is correct
26 Runtime error 93 ms 65536 KB Execution killed with signal 9
27 Correct 1 ms 4444 KB Output is correct
28 Runtime error 109 ms 65536 KB Execution killed with signal 9
29 Correct 1 ms 4440 KB Output is correct
30 Runtime error 90 ms 65536 KB Execution killed with signal 9
31 Correct 1 ms 4444 KB Output is correct
32 Runtime error 93 ms 65536 KB Execution killed with signal 9
33 Correct 4 ms 6488 KB Output is correct
34 Runtime error 98 ms 65536 KB Execution killed with signal 9
35 Runtime error 91 ms 65536 KB Execution killed with signal 9
36 Correct 6 ms 6492 KB Output is correct
37 Runtime error 94 ms 65536 KB Execution killed with signal 9
38 Runtime error 97 ms 65536 KB Execution killed with signal 9
39 Correct 7 ms 6488 KB Output is correct
40 Runtime error 95 ms 65536 KB Execution killed with signal 9
41 Runtime error 96 ms 65536 KB Execution killed with signal 9
42 Correct 10 ms 6492 KB Output is correct
43 Runtime error 97 ms 65536 KB Execution killed with signal 9
44 Runtime error 98 ms 65536 KB Execution killed with signal 9
45 Correct 10 ms 6492 KB Output is correct
46 Runtime error 95 ms 65536 KB Execution killed with signal 9
47 Runtime error 98 ms 65536 KB Execution killed with signal 9
48 Correct 11 ms 6624 KB Output is correct
49 Runtime error 99 ms 65536 KB Execution killed with signal 9
50 Runtime error 104 ms 65536 KB Execution killed with signal 9
51 Correct 14 ms 6488 KB Output is correct
52 Runtime error 102 ms 65536 KB Execution killed with signal 9
53 Runtime error 104 ms 65536 KB Execution killed with signal 9
54 Correct 15 ms 6492 KB Output is correct
55 Runtime error 104 ms 65536 KB Execution killed with signal 9
56 Runtime error 113 ms 65536 KB Execution killed with signal 9
57 Correct 18 ms 6744 KB Output is correct
58 Runtime error 108 ms 65536 KB Execution killed with signal 9
59 Runtime error 104 ms 65536 KB Execution killed with signal 9
60 Correct 20 ms 6748 KB Output is correct
61 Runtime error 107 ms 65536 KB Execution killed with signal 9
62 Runtime error 112 ms 65536 KB Execution killed with signal 9
63 Runtime error 114 ms 65536 KB Execution killed with signal 9
64 Runtime error 112 ms 65536 KB Execution killed with signal 9
65 Runtime error 119 ms 65536 KB Execution killed with signal 9
66 Runtime error 115 ms 65536 KB Execution killed with signal 9
67 Runtime error 132 ms 65536 KB Execution killed with signal 9
68 Runtime error 128 ms 65536 KB Execution killed with signal 9
69 Runtime error 119 ms 65536 KB Execution killed with signal 9
70 Runtime error 114 ms 65536 KB Execution killed with signal 9
71 Runtime error 116 ms 65536 KB Execution killed with signal 9
72 Runtime error 112 ms 65536 KB Execution killed with signal 9
73 Runtime error 94 ms 65536 KB Execution killed with signal 9
74 Runtime error 91 ms 65536 KB Execution killed with signal 9
75 Runtime error 92 ms 65536 KB Execution killed with signal 9
76 Runtime error 90 ms 65536 KB Execution killed with signal 9
77 Runtime error 88 ms 65536 KB Execution killed with signal 9
78 Runtime error 91 ms 65536 KB Execution killed with signal 9
79 Runtime error 92 ms 65536 KB Execution killed with signal 9
80 Runtime error 91 ms 65536 KB Execution killed with signal 9
81 Runtime error 89 ms 65536 KB Execution killed with signal 9
82 Runtime error 91 ms 65536 KB Execution killed with signal 9
83 Runtime error 89 ms 65536 KB Execution killed with signal 9
84 Runtime error 92 ms 65536 KB Execution killed with signal 9
85 Runtime error 88 ms 65536 KB Execution killed with signal 9
86 Runtime error 91 ms 65536 KB Execution killed with signal 9
87 Runtime error 89 ms 65536 KB Execution killed with signal 9
88 Runtime error 92 ms 65536 KB Execution killed with signal 9
89 Runtime error 91 ms 65536 KB Execution killed with signal 9
90 Runtime error 93 ms 65536 KB Execution killed with signal 9
91 Runtime error 92 ms 65536 KB Execution killed with signal 9
92 Runtime error 99 ms 65536 KB Execution killed with signal 9