oj.uz

답안 #1050696

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1050696 2024-08-09T12:45:11 Z kvintsekstakord Mecho (IOI09_mecho) C++17
25 / 100
 162 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;

int N, S;
char forest[1000][1000];
int btime[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 = 2000000;
    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;

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

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

    return 0;
}

Compilation message

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

Subtask #1
25.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Runtime error 97 ms 65536 KB Execution killed with signal 9
8 Correct 0 ms 2396 KB Output is correct
9 Correct 47 ms 36428 KB Output is correct
10 Correct 13 ms 7260 KB Output is correct
11 Correct 2 ms 3164 KB Output is correct
12 Incorrect 1 ms 4700 KB Output isn't correct
13 Runtime error 72 ms 65536 KB Execution killed with signal 9
14 Runtime error 74 ms 65536 KB Execution killed with signal 9
15 Correct 1 ms 2392 KB Output is correct
16 Runtime error 162 ms 65536 KB Execution killed with signal 9
17 Correct 1 ms 2392 KB Output is correct
18 Runtime error 96 ms 65536 KB Execution killed with signal 9
19 Correct 1 ms 2392 KB Output is correct
20 Runtime error 92 ms 65536 KB Execution killed with signal 9
21 Correct 0 ms 2392 KB Output is correct
22 Runtime error 105 ms 65536 KB Execution killed with signal 9
23 Correct 1 ms 4700 KB Output is correct
24 Runtime error 91 ms 65536 KB Execution killed with signal 9
25 Correct 1 ms 4700 KB Output is correct
26 Runtime error 104 ms 65536 KB Execution killed with signal 9
27 Correct 1 ms 4700 KB Output is correct
28 Runtime error 91 ms 65536 KB Execution killed with signal 9
29 Correct 1 ms 4700 KB Output is correct
30 Runtime error 91 ms 65536 KB Execution killed with signal 9
31 Correct 1 ms 4700 KB Output is correct
32 Runtime error 89 ms 65536 KB Execution killed with signal 9
33 Correct 4 ms 4700 KB Output is correct
34 Runtime error 93 ms 65536 KB Execution killed with signal 9
35 Runtime error 95 ms 65536 KB Execution killed with signal 9
36 Correct 5 ms 4700 KB Output is correct
37 Runtime error 93 ms 65536 KB Execution killed with signal 9
38 Runtime error 100 ms 65536 KB Execution killed with signal 9
39 Correct 7 ms 4788 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 8 ms 4696 KB Output is correct
43 Runtime error 98 ms 65536 KB Execution killed with signal 9
44 Runtime error 109 ms 65536 KB Execution killed with signal 9
45 Correct 10 ms 4884 KB Output is correct
46 Runtime error 111 ms 65536 KB Execution killed with signal 9
47 Runtime error 106 ms 65536 KB Execution killed with signal 9
48 Correct 11 ms 4696 KB Output is correct
49 Runtime error 99 ms 65536 KB Execution killed with signal 9
50 Runtime error 105 ms 65536 KB Execution killed with signal 9
51 Correct 13 ms 4956 KB Output is correct
52 Runtime error 103 ms 65536 KB Execution killed with signal 9
53 Runtime error 108 ms 65536 KB Execution killed with signal 9
54 Correct 15 ms 4956 KB Output is correct
55 Runtime error 105 ms 65536 KB Execution killed with signal 9
56 Runtime error 110 ms 65536 KB Execution killed with signal 9
57 Correct 18 ms 4956 KB Output is correct
58 Runtime error 106 ms 65536 KB Execution killed with signal 9
59 Runtime error 113 ms 65536 KB Execution killed with signal 9
60 Correct 20 ms 4956 KB Output is correct
61 Runtime error 107 ms 65536 KB Execution killed with signal 9
62 Runtime error 108 ms 65536 KB Execution killed with signal 9
63 Runtime error 113 ms 65536 KB Execution killed with signal 9
64 Runtime error 119 ms 65536 KB Execution killed with signal 9
65 Runtime error 115 ms 65536 KB Execution killed with signal 9
66 Runtime error 133 ms 65536 KB Execution killed with signal 9
67 Runtime error 115 ms 65536 KB Execution killed with signal 9
68 Runtime error 146 ms 65536 KB Execution killed with signal 9
69 Runtime error 138 ms 65536 KB Execution killed with signal 9
70 Runtime error 123 ms 65536 KB Execution killed with signal 9
71 Runtime error 116 ms 65536 KB Execution killed with signal 9
72 Runtime error 115 ms 65536 KB Execution killed with signal 9
73 Runtime error 93 ms 65536 KB Execution killed with signal 9
74 Runtime error 93 ms 65536 KB Execution killed with signal 9
75 Runtime error 93 ms 65536 KB Execution killed with signal 9
76 Runtime error 89 ms 65536 KB Execution killed with signal 9
77 Runtime error 111 ms 65536 KB Execution killed with signal 9
78 Runtime error 92 ms 65536 KB Execution killed with signal 9
79 Runtime error 94 ms 65536 KB Execution killed with signal 9
80 Runtime error 107 ms 65536 KB Execution killed with signal 9
81 Runtime error 101 ms 65536 KB Execution killed with signal 9
82 Runtime error 97 ms 65536 KB Execution killed with signal 9
83 Runtime error 92 ms 65536 KB Execution killed with signal 9
84 Runtime error 91 ms 65536 KB Execution killed with signal 9
85 Runtime error 97 ms 65536 KB Execution killed with signal 9
86 Runtime error 102 ms 65536 KB Execution killed with signal 9
87 Runtime error 91 ms 65536 KB Execution killed with signal 9
88 Runtime error 92 ms 65536 KB Execution killed with signal 9
89 Runtime error 99 ms 65536 KB Execution killed with signal 9
90 Runtime error 92 ms 65536 KB Execution killed with signal 9
91 Runtime error 106 ms 65536 KB Execution killed with signal 9
92 Runtime error 103 ms 65536 KB Execution killed with signal 9