oj.uz

답안 #572133

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
572133 2022-06-03T18:09:27 Z Vanilla Mecho (IOI09_mecho) C++17
21 / 100
 308 ms 3200 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 810;
char a [maxn][maxn];
char c [maxn][maxn];
bool vis [maxn][maxn];
bool bad [maxn][maxn];
int n,s, sx, sy, ex, ey;
queue <pair <int, int> > startq;
int dx[] = {-1, 0, 1, -1};
int dy[] = {0, 1, 0, -1};

void propagate_bees(queue <pair <int, int> > &bee) {
    int k = bee.size();
    for (int i = 0; i < k; i++){
        int x = bee.front().first, y = bee.front().second;
        bee.pop();
        for (int j = 0; j < 4; j++){
            int nx = x + dx[j], ny = y + dy[j];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n || 
                c[nx][ny] == 'T' || c[nx][ny] == 'D' || c[nx][ny] == 'H') continue;
            c[nx][ny] = 'H';
            bee.push({nx, ny});
        }
    }
}

bool check (int minutes) {
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            vis[i][j] = 0;
            c[i][j] = a[i][j];
        }
    }
    queue <pair <int, int> > bear, bee = startq;
    bear.push({sx, sy}); 
    // move bees for minutes before starting search
    while (minutes--) {
        propagate_bees(bee);
    }
    while (!bear.empty()){
        for (int z = 0; z < s; z++){
            int k = bear.size();
            for (int i = 0; i < k; i++){
                int x = bear.front().first, y = bear.front().second;
                bear.pop();
                if (c[x][y] == 'H') continue;
                for (int j = 0; j < 4; j++){
                    int nx = x + dx[j], ny = y + dy[j];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= n || vis[nx][ny] || 
                        c[nx][ny] == 'T' || c[nx][ny] == 'H') continue;
                    if (c[nx][ny] == 'D') return 1;
                    vis[nx][ny] = 1;
                    bear.push({nx, ny});
                }
            }
        }
        int k = bee.size();
        propagate_bees(bee);
    }
    return 0;

}

int main() {
    cin >> n >> s;
    for (int i = 0; i < n; i++){
        cin >> a[i];
        for (int j = 0; j < n; j++){
            if (a[i][j] == 'M') {
                sx = i, sy = j;
                a[i][j] = 'G';
            }
            if (a[i][j] == 'D') {
                ex = i, ey = j;
            }
            if (a[i][j] == 'H') {
                startq.push({i,j});
            }
        }
    }
    // check(0);
    int l = 0, r = maxn * maxn, rs = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            rs = mid;
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }
    cout << rs;
    return 0;
}

Compilation message

mecho.cpp: In function 'bool check(int)':
mecho.cpp:59:13: warning: unused variable 'k' [-Wunused-variable]
   59 |         int k = bee.size();
      |             ^

Subtask #1
21.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 340 KB Output is correct
2 Incorrect 3 ms 212 KB Output isn't correct
3 Correct 3 ms 308 KB Output is correct
4 Incorrect 3 ms 212 KB Output isn't correct
5 Correct 3 ms 344 KB Output is correct
6 Incorrect 3 ms 340 KB Output isn't correct
7 Incorrect 247 ms 2864 KB Output isn't correct
8 Correct 3 ms 360 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 4 ms 340 KB Output is correct
12 Incorrect 56 ms 340 KB Output isn't correct
13 Correct 4 ms 340 KB Output is correct
14 Correct 5 ms 468 KB Output is correct
15 Incorrect 4 ms 340 KB Output isn't correct
16 Incorrect 60 ms 312 KB Output isn't correct
17 Incorrect 3 ms 340 KB Output isn't correct
18 Incorrect 55 ms 340 KB Output isn't correct
19 Incorrect 3 ms 340 KB Output isn't correct
20 Incorrect 57 ms 340 KB Output isn't correct
21 Incorrect 3 ms 340 KB Output isn't correct
22 Incorrect 56 ms 340 KB Output isn't correct
23 Incorrect 4 ms 340 KB Output isn't correct
24 Incorrect 56 ms 340 KB Output isn't correct
25 Incorrect 3 ms 468 KB Output isn't correct
26 Incorrect 56 ms 468 KB Output isn't correct
27 Incorrect 4 ms 440 KB Output isn't correct
28 Incorrect 56 ms 480 KB Output isn't correct
29 Incorrect 4 ms 468 KB Output isn't correct
30 Incorrect 55 ms 468 KB Output isn't correct
31 Incorrect 4 ms 468 KB Output isn't correct
32 Incorrect 55 ms 488 KB Output isn't correct
33 Incorrect 7 ms 1276 KB Output isn't correct
34 Incorrect 58 ms 1212 KB Output isn't correct
35 Correct 38 ms 1236 KB Output is correct
36 Incorrect 8 ms 1340 KB Output isn't correct
37 Incorrect 63 ms 1408 KB Output isn't correct
38 Correct 48 ms 1492 KB Output is correct
39 Incorrect 9 ms 1476 KB Output isn't correct
40 Incorrect 60 ms 1576 KB Output isn't correct
41 Correct 59 ms 1572 KB Output is correct
42 Incorrect 10 ms 1748 KB Output isn't correct
43 Incorrect 61 ms 1728 KB Output isn't correct
44 Correct 73 ms 1756 KB Output is correct
45 Incorrect 11 ms 1876 KB Output isn't correct
46 Incorrect 67 ms 1848 KB Output isn't correct
47 Correct 86 ms 1876 KB Output is correct
48 Incorrect 12 ms 2064 KB Output isn't correct
49 Incorrect 65 ms 2096 KB Output isn't correct
50 Correct 102 ms 2004 KB Output is correct
51 Incorrect 13 ms 2260 KB Output isn't correct
52 Incorrect 67 ms 2268 KB Output isn't correct
53 Correct 132 ms 2284 KB Output is correct
54 Incorrect 15 ms 2468 KB Output isn't correct
55 Incorrect 67 ms 2388 KB Output isn't correct
56 Correct 146 ms 2388 KB Output is correct
57 Incorrect 16 ms 2592 KB Output isn't correct
58 Incorrect 71 ms 2640 KB Output isn't correct
59 Correct 164 ms 2764 KB Output is correct
60 Incorrect 19 ms 2752 KB Output isn't correct
61 Incorrect 70 ms 2832 KB Output isn't correct
62 Correct 187 ms 2840 KB Output is correct
63 Incorrect 279 ms 2832 KB Output isn't correct
64 Incorrect 81 ms 2832 KB Output isn't correct
65 Incorrect 86 ms 2772 KB Output isn't correct
66 Incorrect 94 ms 2836 KB Output isn't correct
67 Incorrect 80 ms 2832 KB Output isn't correct
68 Incorrect 245 ms 2892 KB Output isn't correct
69 Incorrect 225 ms 2872 KB Output isn't correct
70 Incorrect 263 ms 2876 KB Output isn't correct
71 Incorrect 262 ms 2872 KB Output isn't correct
72 Incorrect 239 ms 2872 KB Output isn't correct
73 Incorrect 262 ms 3136 KB Output isn't correct
74 Incorrect 257 ms 3124 KB Output isn't correct
75 Incorrect 261 ms 3140 KB Output isn't correct
76 Incorrect 269 ms 3200 KB Output isn't correct
77 Incorrect 273 ms 3132 KB Output isn't correct
78 Correct 308 ms 3092 KB Output is correct
79 Correct 251 ms 3132 KB Output is correct
80 Correct 262 ms 3028 KB Output is correct
81 Correct 272 ms 3096 KB Output is correct
82 Correct 265 ms 3092 KB Output is correct
83 Incorrect 191 ms 2972 KB Output isn't correct
84 Incorrect 204 ms 3028 KB Output isn't correct
85 Incorrect 193 ms 2960 KB Output isn't correct
86 Incorrect 194 ms 3148 KB Output isn't correct
87 Incorrect 195 ms 3148 KB Output isn't correct
88 Incorrect 186 ms 2900 KB Output isn't correct
89 Incorrect 184 ms 3004 KB Output isn't correct
90 Incorrect 184 ms 3004 KB Output isn't correct
91 Incorrect 185 ms 3004 KB Output isn't correct
92 Incorrect 190 ms 3004 KB Output isn't correct