답안 #264668

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
264668	2020-08-14T08:19:17 Z	WLZ	Mecho (IOI09_mecho)	C++14	38 / 100	1000 ms	7188 KB

mecho

#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 + 1) / 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;
    } 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

38.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	Incorrect	1 ms	384 KB	Output isn't correct
6	Incorrect	1 ms	384 KB	Output isn't correct
7	Execution timed out	1008 ms	6920 KB	Time limit exceeded
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Incorrect	1 ms	384 KB	Output isn't correct
11	Incorrect	1 ms	384 KB	Output isn't correct
12	Incorrect	3 ms	384 KB	Output isn't correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct
15	Correct	1 ms	384 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	1 ms	384 KB	Output is correct
18	Correct	1 ms	384 KB	Output is correct
19	Correct	1 ms	384 KB	Output is correct
20	Correct	1 ms	384 KB	Output is correct
21	Correct	1 ms	384 KB	Output is correct
22	Correct	2 ms	384 KB	Output is correct
23	Correct	1 ms	384 KB	Output is correct
24	Correct	2 ms	384 KB	Output is correct
25	Correct	1 ms	384 KB	Output is correct
26	Correct	2 ms	384 KB	Output is correct
27	Correct	1 ms	512 KB	Output is correct
28	Correct	2 ms	384 KB	Output is correct
29	Correct	1 ms	384 KB	Output is correct
30	Correct	3 ms	384 KB	Output is correct
31	Correct	1 ms	384 KB	Output is correct
32	Correct	3 ms	384 KB	Output is correct
33	Correct	14 ms	1796 KB	Output is correct
34	Correct	52 ms	1632 KB	Output is correct
35	Incorrect	134 ms	1720 KB	Output isn't correct
36	Correct	19 ms	2208 KB	Output is correct
37	Correct	69 ms	2160 KB	Output is correct
38	Incorrect	175 ms	2048 KB	Output isn't correct
39	Correct	23 ms	2424 KB	Output is correct
40	Correct	85 ms	2432 KB	Output is correct
41	Incorrect	234 ms	2456 KB	Output isn't correct
42	Correct	35 ms	3056 KB	Output is correct
43	Correct	112 ms	2912 KB	Output is correct
44	Incorrect	322 ms	2980 KB	Output isn't correct
45	Correct	34 ms	3408 KB	Output is correct
46	Correct	130 ms	3540 KB	Output is correct
47	Incorrect	368 ms	3408 KB	Output isn't correct
48	Correct	42 ms	4272 KB	Output is correct
49	Correct	168 ms	4048 KB	Output is correct
50	Incorrect	434 ms	4228 KB	Output isn't correct
51	Correct	53 ms	4688 KB	Output is correct
52	Correct	188 ms	4772 KB	Output is correct
53	Incorrect	526 ms	4688 KB	Output isn't correct
54	Correct	58 ms	5448 KB	Output is correct
55	Correct	212 ms	5412 KB	Output is correct
56	Incorrect	558 ms	5452 KB	Output isn't correct
57	Correct	67 ms	6152 KB	Output is correct
58	Correct	247 ms	6208 KB	Output is correct
59	Incorrect	665 ms	6236 KB	Output isn't correct
60	Correct	75 ms	6876 KB	Output is correct
61	Correct	288 ms	6792 KB	Output is correct
62	Incorrect	741 ms	6792 KB	Output isn't correct
63	Incorrect	920 ms	6832 KB	Output isn't correct
64	Incorrect	941 ms	6948 KB	Output isn't correct
65	Incorrect	953 ms	6904 KB	Output isn't correct
66	Incorrect	988 ms	6944 KB	Output isn't correct
67	Execution timed out	1024 ms	6904 KB	Time limit exceeded
68	Incorrect	906 ms	6840 KB	Output isn't correct
69	Incorrect	808 ms	7024 KB	Output isn't correct
70	Incorrect	882 ms	6808 KB	Output isn't correct
71	Incorrect	901 ms	6864 KB	Output isn't correct
72	Correct	807 ms	7056 KB	Output is correct
73	Correct	782 ms	6952 KB	Output is correct
74	Correct	869 ms	7076 KB	Output is correct
75	Correct	924 ms	7008 KB	Output is correct
76	Correct	930 ms	6956 KB	Output is correct
77	Correct	935 ms	6924 KB	Output is correct
78	Correct	890 ms	7188 KB	Output is correct
79	Correct	871 ms	6836 KB	Output is correct
80	Correct	876 ms	7088 KB	Output is correct
81	Correct	903 ms	6960 KB	Output is correct
82	Correct	895 ms	6836 KB	Output is correct
83	Execution timed out	1026 ms	6884 KB	Time limit exceeded
84	Execution timed out	1004 ms	6840 KB	Time limit exceeded
85	Execution timed out	1059 ms	6888 KB	Time limit exceeded
86	Execution timed out	1032 ms	6832 KB	Time limit exceeded
87	Execution timed out	1056 ms	6860 KB	Time limit exceeded
88	Execution timed out	1064 ms	7044 KB	Time limit exceeded
89	Correct	966 ms	7060 KB	Output is correct
90	Correct	995 ms	6932 KB	Output is correct
91	Correct	919 ms	7020 KB	Output is correct
92	Correct	942 ms	6924 KB	Output is correct