oj.uz

답안 #1049576

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1049576 2024-08-08T23:46:55 Z kvintsekstakord Mecho (IOI09_mecho) C++17
15 / 100
 125 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));
            }
        }
    }

    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

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.0 / 100.0

# 결과 실행 시간 메모리 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 1 ms 4440 KB Output is correct
6 Correct 0 ms 4444 KB Output is correct
7 Runtime error 87 ms 65536 KB Execution killed with signal 9
8 Incorrect 1 ms 4440 KB Output isn't correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 0 ms 4440 KB Output is correct
11 Correct 0 ms 4444 KB Output is correct
12 Incorrect 1 ms 6492 KB Output isn't correct
13 Runtime error 90 ms 65536 KB Execution killed with signal 9
14 Runtime error 69 ms 65536 KB Execution killed with signal 9
15 Incorrect 1 ms 4440 KB Output isn't correct
16 Correct 0 ms 4444 KB Output is correct
17 Incorrect 1 ms 6492 KB Output isn't correct
18 Correct 1 ms 6492 KB Output is correct
19 Incorrect 1 ms 6492 KB Output isn't correct
20 Correct 1 ms 6492 KB Output is correct
21 Incorrect 1 ms 6492 KB Output isn't correct
22 Correct 1 ms 6492 KB Output is correct
23 Incorrect 1 ms 6492 KB Output isn't correct
24 Correct 1 ms 6492 KB Output is correct
25 Incorrect 1 ms 6492 KB Output isn't correct
26 Correct 1 ms 6492 KB Output is correct
27 Incorrect 1 ms 6492 KB Output isn't correct
28 Correct 1 ms 6492 KB Output is correct
29 Incorrect 1 ms 6492 KB Output isn't correct
30 Correct 1 ms 6488 KB Output is correct
31 Incorrect 1 ms 8540 KB Output isn't correct
32 Correct 1 ms 8540 KB Output is correct
33 Incorrect 7 ms 12892 KB Output isn't correct
34 Correct 6 ms 12864 KB Output is correct
35 Runtime error 68 ms 65536 KB Execution killed with signal 9
36 Incorrect 8 ms 12892 KB Output isn't correct
37 Correct 7 ms 13000 KB Output is correct
38 Runtime error 104 ms 65536 KB Execution killed with signal 9
39 Incorrect 11 ms 12888 KB Output isn't correct
40 Correct 9 ms 12888 KB Output is correct
41 Runtime error 77 ms 65536 KB Execution killed with signal 9
42 Incorrect 12 ms 13144 KB Output isn't correct
43 Correct 11 ms 13148 KB Output is correct
44 Runtime error 73 ms 65536 KB Execution killed with signal 9
45 Incorrect 14 ms 15196 KB Output isn't correct
46 Correct 13 ms 15196 KB Output is correct
47 Runtime error 90 ms 65536 KB Execution killed with signal 9
48 Incorrect 16 ms 17240 KB Output isn't correct
49 Correct 16 ms 17244 KB Output is correct
50 Runtime error 75 ms 65536 KB Execution killed with signal 9
51 Incorrect 20 ms 17240 KB Output isn't correct
52 Correct 18 ms 17244 KB Output is correct
53 Runtime error 77 ms 65536 KB Execution killed with signal 9
54 Incorrect 23 ms 17496 KB Output isn't correct
55 Correct 27 ms 17488 KB Output is correct
56 Runtime error 82 ms 65536 KB Execution killed with signal 9
57 Incorrect 26 ms 17568 KB Output isn't correct
58 Correct 24 ms 17500 KB Output is correct
59 Runtime error 83 ms 65536 KB Execution killed with signal 9
60 Incorrect 28 ms 17488 KB Output isn't correct
61 Correct 27 ms 17488 KB Output is correct
62 Runtime error 95 ms 65536 KB Execution killed with signal 9
63 Correct 78 ms 17488 KB Output is correct
64 Correct 125 ms 17500 KB Output is correct
65 Correct 105 ms 17500 KB Output is correct
66 Incorrect 98 ms 17720 KB Output isn't correct
67 Correct 80 ms 17488 KB Output is correct
68 Correct 46 ms 17492 KB Output is correct
69 Correct 45 ms 17500 KB Output is correct
70 Correct 43 ms 17488 KB Output is correct
71 Correct 40 ms 17488 KB Output is correct
72 Incorrect 36 ms 17488 KB Output isn't correct
73 Runtime error 88 ms 65536 KB Execution killed with signal 9
74 Runtime error 84 ms 65536 KB Execution killed with signal 9
75 Runtime error 97 ms 65536 KB Execution killed with signal 9
76 Runtime error 94 ms 65536 KB Execution killed with signal 9
77 Runtime error 90 ms 65536 KB Execution killed with signal 9
78 Runtime error 86 ms 65536 KB Execution killed with signal 9
79 Runtime error 84 ms 65536 KB Execution killed with signal 9
80 Runtime error 85 ms 65536 KB Execution killed with signal 9
81 Runtime error 86 ms 65536 KB Execution killed with signal 9
82 Runtime error 84 ms 65536 KB Execution killed with signal 9
83 Runtime error 87 ms 65536 KB Execution killed with signal 9
84 Runtime error 88 ms 65536 KB Execution killed with signal 9
85 Runtime error 98 ms 65536 KB Execution killed with signal 9
86 Runtime error 92 ms 65536 KB Execution killed with signal 9
87 Runtime error 87 ms 65536 KB Execution killed with signal 9
88 Runtime error 84 ms 65536 KB Execution killed with signal 9
89 Runtime error 84 ms 65536 KB Execution killed with signal 9
90 Runtime error 105 ms 65536 KB Execution killed with signal 9
91 Runtime error 101 ms 65536 KB Execution killed with signal 9
92 Runtime error 108 ms 65536 KB Execution killed with signal 9