oj.uz

답안 #264690

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
264690 2020-08-14T08:24:18 Z WLZ Mecho (IOI09_mecho) C++14
24 / 100
 988 ms 6312 KB 
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const vector<int> dx = {0, 0, -1, 1};
const vector<int> dy = {1, -1, 0, 0};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, s;
  cin >> n >> s;
  vector<string> grid(n);
  queue< pair<int, int> > q;
  vector< vector<int> > dist1(n, vector<int>(n, -1));
  int mr, mc, dr, dc;
  for (int i = 0; i < n; i++) {
    cin >> grid[i];
    for (int j = 0; j < n; j++) {
      if (grid[i][j] == 'M') {
        mr = i; mc = j;
      } else if (grid[i][j] == 'H') {
        q.push({i, j});
        dist1[i][j] = 0;
      } else if (grid[i][j] == 'D') {
        dr = i; dc = j;
      }
    }
  }
  while (!q.empty()) {
    int r = q.front().first, c = q.front().second;
    q.pop();
    for (int k = 0; k < 4; k++) {
      int nr = r + dx[k], nc = c + dy[k];
      if (nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] == 'T' || dist1[nr][nc] != -1) {
        continue;
      }
      dist1[nr][nc] = dist1[r][c] + s;
      q.push({nr, nc});
    }
  }
  int lo = 0, hi = n * n, ans = -1;
  for (int i = 0; i < 50; i++) {
    int mid = (lo + hi) / 2;
    //cout << mid << endl;
    vector< vector<int> > dist2(n, vector<int>(n, INF));
    dist2[mr][mc] = s * mid;
    if (dist2[mr][mc] >= dist1[mr][mc]) {
      hi = mid - 1;
      continue;
    }
    q.push({mr, mc});
    while (!q.empty()) {
      int r = q.front().first, c = q.front().second;
      //cout << r << ' ' << c << endl;
      q.pop();
      for (int k = 0; k < 4; k++) {
        int nr = r + dx[k], nc = c + dy[k];
        if (nr < 0 || nr >= n || nc < 0 || nc >= n || dist2[r][c] + 1 >= dist2[nr][nc] || (!(nr == dr && nc == dc) && dist2[r][c] + 1 >= dist1[nr][nc]) || grid[nr][nc] == 'T') {
          continue;
        }
        dist2[nr][nc] = dist2[r][c] + 1;
        q.push({nr, nc});
      }
    }
    if (dist2[dr][dc] <= dist1[dr][dc]) {
      ans = mid;
      lo = mid - 1;
    } else {
      hi = mid - 1;
    }
  }
  cout << ans << '\n';
  return 0;
}

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:47:17: warning: 'mc' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |     dist2[mr][mc] = s * mid;
      |                 ^
mecho.cpp:47:13: warning: 'mr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |     dist2[mr][mc] = s * mid;
      |             ^
mecho.cpp:66:21: warning: 'dc' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |     if (dist2[dr][dc] <= dist1[dr][dc]) {
      |                     ^
mecho.cpp:66:17: warning: 'dr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |     if (dist2[dr][dc] <= dist1[dr][dc]) {
      |                 ^

Subtask #1
24.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Correct 1 ms 384 KB Output is correct
6 Incorrect 1 ms 384 KB Output isn't correct
7 Incorrect 577 ms 6268 KB Output isn't correct
8 Correct 1 ms 384 KB Output is correct
9 Incorrect 1 ms 384 KB Output isn't correct
10 Incorrect 1 ms 384 KB Output isn't correct
11 Correct 1 ms 384 KB Output is correct
12 Incorrect 1 ms 384 KB Output isn't correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Incorrect 1 ms 384 KB Output isn't correct
17 Correct 1 ms 384 KB Output is correct
18 Incorrect 1 ms 384 KB Output isn't correct
19 Correct 1 ms 384 KB Output is correct
20 Incorrect 1 ms 384 KB Output isn't correct
21 Correct 1 ms 384 KB Output is correct
22 Incorrect 1 ms 384 KB Output isn't correct
23 Correct 1 ms 384 KB Output is correct
24 Incorrect 1 ms 384 KB Output isn't correct
25 Incorrect 1 ms 384 KB Output isn't correct
26 Incorrect 1 ms 384 KB Output isn't correct
27 Correct 1 ms 384 KB Output is correct
28 Incorrect 1 ms 384 KB Output isn't correct
29 Incorrect 2 ms 384 KB Output isn't correct
30 Correct 1 ms 384 KB Output is correct
31 Incorrect 1 ms 384 KB Output isn't correct
32 Incorrect 2 ms 384 KB Output isn't correct
33 Correct 14 ms 1508 KB Output is correct
34 Incorrect 19 ms 1504 KB Output isn't correct
35 Incorrect 145 ms 1500 KB Output isn't correct
36 Correct 21 ms 1852 KB Output is correct
37 Correct 23 ms 1844 KB Output is correct
38 Incorrect 200 ms 1848 KB Output isn't correct
39 Incorrect 23 ms 2224 KB Output isn't correct
40 Incorrect 25 ms 2224 KB Output isn't correct
41 Incorrect 234 ms 2256 KB Output isn't correct
42 Incorrect 29 ms 2832 KB Output isn't correct
43 Incorrect 31 ms 2836 KB Output isn't correct
44 Incorrect 350 ms 2656 KB Output isn't correct
45 Correct 50 ms 3104 KB Output is correct
46 Incorrect 39 ms 3104 KB Output isn't correct
47 Incorrect 352 ms 3216 KB Output isn't correct
48 Correct 48 ms 3804 KB Output is correct
49 Incorrect 57 ms 3640 KB Output isn't correct
50 Incorrect 441 ms 3672 KB Output isn't correct
51 Correct 49 ms 4364 KB Output is correct
52 Incorrect 53 ms 4176 KB Output isn't correct
53 Incorrect 534 ms 4208 KB Output isn't correct
54 Correct 58 ms 4936 KB Output is correct
55 Correct 70 ms 4928 KB Output is correct
56 Incorrect 712 ms 4928 KB Output isn't correct
57 Incorrect 87 ms 5560 KB Output isn't correct
58 Incorrect 70 ms 5580 KB Output isn't correct
59 Correct 721 ms 5448 KB Output is correct
60 Correct 78 ms 6288 KB Output is correct
61 Incorrect 85 ms 6252 KB Output isn't correct
62 Incorrect 914 ms 6260 KB Output isn't correct
63 Correct 796 ms 6152 KB Output is correct
64 Incorrect 988 ms 6148 KB Output isn't correct
65 Incorrect 918 ms 6312 KB Output isn't correct
66 Incorrect 780 ms 6152 KB Output isn't correct
67 Correct 615 ms 6204 KB Output is correct
68 Correct 356 ms 6184 KB Output is correct
69 Incorrect 328 ms 6168 KB Output isn't correct
70 Incorrect 249 ms 6200 KB Output isn't correct
71 Incorrect 233 ms 6192 KB Output isn't correct
72 Incorrect 110 ms 6232 KB Output isn't correct
73 Correct 405 ms 6200 KB Output is correct
74 Correct 322 ms 6208 KB Output is correct
75 Correct 413 ms 6200 KB Output is correct
76 Correct 342 ms 6240 KB Output is correct
77 Correct 326 ms 6240 KB Output is correct
78 Correct 442 ms 6200 KB Output is correct
79 Incorrect 309 ms 6308 KB Output isn't correct
80 Incorrect 437 ms 6196 KB Output isn't correct
81 Incorrect 442 ms 6196 KB Output isn't correct
82 Incorrect 396 ms 6292 KB Output isn't correct
83 Correct 534 ms 6240 KB Output is correct
84 Incorrect 432 ms 6224 KB Output isn't correct
85 Incorrect 549 ms 6224 KB Output isn't correct
86 Incorrect 481 ms 6288 KB Output isn't correct
87 Incorrect 503 ms 6196 KB Output isn't correct
88 Correct 606 ms 6292 KB Output is correct
89 Correct 545 ms 6208 KB Output is correct
90 Incorrect 542 ms 6240 KB Output isn't correct
91 Correct 555 ms 6304 KB Output is correct
92 Incorrect 526 ms 6252 KB Output isn't correct