oj.uz

답안 #912785

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
912785 2024-01-19T22:26:59 Z Glauco Mecho (IOI09_mecho) C++17
19 / 100
 211 ms 5392 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, s; cin >> n >> s;
  vector<vector<char>> g(n, vector<char>(n));
  for(auto &i : g) for(auto &j : i) cin >> j;

  queue<array<int, 3>> q;
  pair<int, int> start;
  for(int i = 0; i < n; i++) for(int j = 0; j < n; j++){
    if(g[i][j] == 'M') start = {i, j};
    if(g[i][j] == 'H') q.push({i, j, 0});
  }

  vector<vector<int>> free(n, vector<int>(n, 1e9));
  while(!q.empty()){
    auto [x, y, d] = q.front(); q.pop();
    
    if(x < 0 || y < 0 || x >= n || y >= n) continue;
    if(g[x][y] != 'H' && g[x][y] != 'G') continue;
    if(free[x][y] != 1e9) continue;
    free[x][y] = d; 

    q.push({x+1, y, d+1});
    q.push({x-1, y, d+1});
    q.push({x, y+1, d+1});
    q.push({x, y-1, d+1});
  }

  int l = -1, r = 1e8;
  while(l < r-1){
    int m = (l+r)/2;

    bool ok = 0;
    vector<vector<bool>> vis(n, vector<bool>(n));
    queue<array<int, 4>> b; b.push({start.first, start.second, m, s});
    while(!b.empty()){
      auto [x, y, d, st] = b.front(); b.pop();

      if(x < 0 || y < 0 || x >= n || y >= n) continue;

      if(st == 0){
        st = s;
        d++;
      }

      if(vis[x][y]) continue; vis[x][y] = 1;
      if(g[x][y] == 'T') continue;
      if(free[x][y] < d || (free[x][y] == d && st == s)) continue;
      
      if(g[x][y] == 'D'){
        ok = 1;
        break;
      }

      b.push({x+1, y, d, st-1});
      b.push({x-1, y, d, st-1});
      b.push({x, y+1, d, st-1});
      b.push({x, y-1, d, st-1});
    }

    if(ok) l = m;
    else r = m;
  }

  cout << l;
}

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:48:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   48 |       if(vis[x][y]) continue; vis[x][y] = 1;
      |       ^~
mecho.cpp:48:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   48 |       if(vis[x][y]) continue; vis[x][y] = 1;
      |                               ^~~

Subtask #1
19.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Incorrect 153 ms 4260 KB Output isn't correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Incorrect 0 ms 600 KB Output isn't correct
12 Incorrect 1 ms 348 KB Output isn't correct
13 Incorrect 1 ms 348 KB Output isn't correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Correct 0 ms 348 KB Output is correct
18 Incorrect 0 ms 348 KB Output isn't correct
19 Correct 1 ms 348 KB Output is correct
20 Incorrect 1 ms 348 KB Output isn't correct
21 Correct 1 ms 348 KB Output is correct
22 Incorrect 1 ms 348 KB Output isn't correct
23 Correct 1 ms 344 KB Output is correct
24 Incorrect 1 ms 348 KB Output isn't correct
25 Correct 1 ms 348 KB Output is correct
26 Incorrect 1 ms 348 KB Output isn't correct
27 Correct 1 ms 348 KB Output is correct
28 Incorrect 1 ms 348 KB Output isn't correct
29 Correct 1 ms 548 KB Output is correct
30 Incorrect 1 ms 348 KB Output isn't correct
31 Correct 1 ms 348 KB Output is correct
32 Incorrect 1 ms 348 KB Output isn't correct
33 Correct 8 ms 860 KB Output is correct
34 Incorrect 8 ms 856 KB Output isn't correct
35 Incorrect 34 ms 1116 KB Output isn't correct
36 Correct 9 ms 1368 KB Output is correct
37 Incorrect 10 ms 1116 KB Output isn't correct
38 Incorrect 48 ms 1116 KB Output isn't correct
39 Correct 11 ms 1372 KB Output is correct
40 Incorrect 12 ms 1372 KB Output isn't correct
41 Incorrect 61 ms 1536 KB Output isn't correct
42 Correct 15 ms 1628 KB Output is correct
43 Incorrect 15 ms 1628 KB Output isn't correct
44 Incorrect 77 ms 1776 KB Output isn't correct
45 Correct 17 ms 1880 KB Output is correct
46 Incorrect 17 ms 1952 KB Output isn't correct
47 Incorrect 93 ms 1972 KB Output isn't correct
48 Correct 20 ms 2136 KB Output is correct
49 Incorrect 20 ms 2140 KB Output isn't correct
50 Incorrect 111 ms 2328 KB Output isn't correct
51 Correct 23 ms 2392 KB Output is correct
52 Incorrect 23 ms 2396 KB Output isn't correct
53 Incorrect 128 ms 2652 KB Output isn't correct
54 Correct 30 ms 2904 KB Output is correct
55 Incorrect 29 ms 2900 KB Output isn't correct
56 Incorrect 154 ms 3152 KB Output isn't correct
57 Correct 31 ms 3160 KB Output is correct
58 Incorrect 32 ms 3300 KB Output isn't correct
59 Incorrect 173 ms 3392 KB Output isn't correct
60 Correct 35 ms 3664 KB Output is correct
61 Incorrect 35 ms 3640 KB Output isn't correct
62 Incorrect 211 ms 3668 KB Output isn't correct
63 Correct 153 ms 3732 KB Output is correct
64 Correct 195 ms 4008 KB Output is correct
65 Incorrect 190 ms 3664 KB Output isn't correct
66 Correct 158 ms 3672 KB Output is correct
67 Correct 161 ms 3664 KB Output is correct
68 Incorrect 68 ms 3788 KB Output isn't correct
69 Correct 67 ms 3676 KB Output is correct
70 Incorrect 61 ms 3672 KB Output isn't correct
71 Incorrect 60 ms 3676 KB Output isn't correct
72 Incorrect 56 ms 3684 KB Output isn't correct
73 Incorrect 105 ms 5252 KB Output isn't correct
74 Incorrect 102 ms 5256 KB Output isn't correct
75 Incorrect 113 ms 5208 KB Output isn't correct
76 Incorrect 119 ms 5392 KB Output isn't correct
77 Incorrect 121 ms 5212 KB Output isn't correct
78 Correct 126 ms 4944 KB Output is correct
79 Incorrect 101 ms 4944 KB Output isn't correct
80 Incorrect 111 ms 5204 KB Output isn't correct
81 Incorrect 130 ms 4944 KB Output isn't correct
82 Incorrect 103 ms 4952 KB Output isn't correct
83 Incorrect 126 ms 4688 KB Output isn't correct
84 Incorrect 132 ms 4832 KB Output isn't correct
85 Incorrect 130 ms 4692 KB Output isn't correct
86 Incorrect 132 ms 4696 KB Output isn't correct
87 Incorrect 139 ms 4952 KB Output isn't correct
88 Incorrect 129 ms 4568 KB Output isn't correct
89 Incorrect 139 ms 4568 KB Output isn't correct
90 Incorrect 156 ms 4596 KB Output isn't correct
91 Incorrect 147 ms 4572 KB Output isn't correct
92 Incorrect 146 ms 4596 KB Output isn't correct