답안 #511170

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
511170	2022-01-15T10:28:25 Z	600Mihnea	Mecho (IOI09_mecho)	C++17	60 / 100	217 ms	15912 KB

mecho

#include <bits/stdc++.h>

using namespace std;

const int N = 1000 + 7;
const int INF = (int) 1e9 + 7;
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};
int n;
int speed;
int r1, c1;
int r2, c2;
int a[N][N];
int dist_m[N][N];
int dist_b[N][N];

vector<pair<int, int>> ord;

void compute(int dist[N][N], vector<pair<int, int>> init) {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      dist[i][j] = INF;
    }
  }

  queue<pair<int, int>> q;
  for (auto &it : init) {
    dist[it.first][it.second] = 0;
    q.push(it);
  }
  while (!q.empty()) {
    auto it = q.front();
    int r = it.first;
    int c = it.second;
    ord.push_back(it);
    q.pop();
    for (int k = 0; k < 4; k++) {
      int rn = r + dr[k];
      int cn = c + dc[k];
      if (a[rn][cn] && dist[rn][cn] == INF) {
        dist[rn][cn] = 1 + dist[r][c];
        q.push({rn, cn});
      }
    }
  }
}

int dist[N][N];
bool ok[N][N];

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);
///freopen ("input", "r", stdin);

  cin >> n >> speed;

  vector<pair<int, int>> bees;

  for (int i = 1; i <= n; i++) {
    string s;
    cin >> s;
    for (int j = 1; j <= n; j++) {
      char ch = s[j - 1];
      if (ch == 'T') {
        a[i][j] = 0;
        continue;
      }
      if (ch == 'G') {
        a[i][j] = 1;
        continue;
      }
      if (ch == 'M') {
        r1 = i;
        c1 = j;
        continue;
      }
      if (ch == 'D') {
        r2 = i;
        c2 = j;
        continue;
      }
      if (ch == 'H') {
        bees.push_back({i, j});
        continue;
      }
    }
  }
  ///cout << r2 << " " << c2 << "\n";
  vector<pair<int, int>> m;
  m.push_back({r1, c1});
  compute(dist_b, bees);
  ord.clear();
  a[r1][c1] = 1;
  a[r2][c2] = 1;
  compute(dist_m, m);

  int low = 0, high = dist_b[r1][c1] - 1, sol = -1;

  while (low <= high) {
    int stay = (low + high) / 2;
  ///  stay = 1;
    ///stay = 3;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        ok[i][j] = 0;
      }
    }
    ok[r1][c1] = 1;
    queue<pair<int, int>> q;
    q.push({r1, c1});
    while (!q.empty()) {
      int r = q.front().first, c = q.front().second;
      q.pop();
      if (ok[r][c]) {
        for (int k = 0; k < 4; k++) {
          int rn = r + dr[k];
          int cn = c + dc[k];
          int the_dist = dist_m[r][c] + 1;
          if (ok[rn][cn] || a[rn][cn] == 0) continue;
          ok[rn][cn] |= ((stay + the_dist / speed) < (dist_b[rn][cn] + (rn == r2 && cn == c2)));

          if (ok[rn][cn]) q.push({rn, cn});
        }
      }
    }

//    cout << " val = " << ok[r2][c2 - 1] << "\n";
 //   exit(0);
 if (0) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (ok[i][j]) {
          if ((stay + (dist_m[i][j] + speed - 1) / speed) > INF / 10 && 0) {
            cout << "? ";
          } else {
            cout << (stay + (dist_m[i][j] + speed - 1) / speed) << " ";
          }
        } else {
          cout << "- ";
        }
        ///cout << ok[i][j] << " ";
      }
      cout << "\n";
    }
    cout << "\n";

    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (ok[i][j]) {
          if (dist_b[i][j] > INF / 10) {
            cout << "? ";
          } else {
            cout << dist_b[i][j] << " ";
          }
        } else {
          cout << "- ";
        }
        ///cout << ok[i][j] << " ";
      }
      cout << "\n";
    }

    exit(0);}
    if (ok[r2][c2]) {
      sol = stay;
      low = stay + 1;
    } else {
      high = stay - 1;
    }
  }

  cout << sol << "\n";
  return 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      int val = dist_m[i][j];
      if (val == INF) {
        cout << "- ";
      } else {
        cout << val << " ";
      }
    }
    cout << "\n";
  }

  return 0;
}

Subtask #1

60.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	460 KB	Output is correct
7	Correct	95 ms	15756 KB	Output is correct
8	Correct	0 ms	460 KB	Output is correct
9	Correct	0 ms	460 KB	Output is correct
10	Correct	1 ms	460 KB	Output is correct
11	Correct	0 ms	460 KB	Output is correct
12	Incorrect	1 ms	1100 KB	Output isn't correct
13	Incorrect	1 ms	972 KB	Output isn't correct
14	Correct	1 ms	1100 KB	Output is correct
15	Correct	0 ms	588 KB	Output is correct
16	Correct	0 ms	588 KB	Output is correct
17	Correct	0 ms	588 KB	Output is correct
18	Correct	1 ms	588 KB	Output is correct
19	Correct	0 ms	716 KB	Output is correct
20	Correct	1 ms	716 KB	Output is correct
21	Correct	1 ms	844 KB	Output is correct
22	Correct	1 ms	844 KB	Output is correct
23	Correct	1 ms	972 KB	Output is correct
24	Correct	1 ms	972 KB	Output is correct
25	Correct	1 ms	1076 KB	Output is correct
26	Correct	1 ms	1100 KB	Output is correct
27	Correct	1 ms	1228 KB	Output is correct
28	Correct	1 ms	1100 KB	Output is correct
29	Correct	2 ms	1228 KB	Output is correct
30	Correct	1 ms	1228 KB	Output is correct
31	Correct	2 ms	1408 KB	Output is correct
32	Correct	1 ms	1228 KB	Output is correct
33	Correct	6 ms	5324 KB	Output is correct
34	Correct	10 ms	5436 KB	Output is correct
35	Incorrect	18 ms	5576 KB	Output isn't correct
36	Correct	8 ms	6192 KB	Output is correct
37	Correct	6 ms	6216 KB	Output is correct
38	Incorrect	23 ms	6472 KB	Output isn't correct
39	Correct	10 ms	6980 KB	Output is correct
40	Correct	9 ms	6980 KB	Output is correct
41	Incorrect	33 ms	7396 KB	Output isn't correct
42	Correct	12 ms	7768 KB	Output is correct
43	Correct	9 ms	7880 KB	Output is correct
44	Incorrect	44 ms	8276 KB	Output isn't correct
45	Correct	12 ms	8712 KB	Output is correct
46	Correct	11 ms	8708 KB	Output is correct
47	Incorrect	49 ms	9284 KB	Output isn't correct
48	Correct	16 ms	9536 KB	Output is correct
49	Correct	15 ms	9516 KB	Output is correct
50	Incorrect	80 ms	10316 KB	Output isn't correct
51	Correct	16 ms	10460 KB	Output is correct
52	Correct	15 ms	10436 KB	Output is correct
53	Incorrect	69 ms	11256 KB	Output isn't correct
54	Correct	19 ms	11304 KB	Output is correct
55	Correct	19 ms	11380 KB	Output is correct
56	Incorrect	80 ms	12292 KB	Output isn't correct
57	Correct	19 ms	12220 KB	Output is correct
58	Correct	21 ms	12220 KB	Output is correct
59	Incorrect	96 ms	13324 KB	Output isn't correct
60	Correct	25 ms	13240 KB	Output is correct
61	Correct	27 ms	13248 KB	Output is correct
62	Incorrect	110 ms	14448 KB	Output isn't correct
63	Correct	116 ms	13624 KB	Output is correct
64	Correct	187 ms	13740 KB	Output is correct
65	Correct	217 ms	13784 KB	Output is correct
66	Correct	135 ms	13696 KB	Output is correct
67	Correct	124 ms	13756 KB	Output is correct
68	Correct	62 ms	13732 KB	Output is correct
69	Correct	69 ms	13720 KB	Output is correct
70	Correct	54 ms	13684 KB	Output is correct
71	Correct	54 ms	13736 KB	Output is correct
72	Incorrect	52 ms	13680 KB	Output isn't correct
73	Incorrect	69 ms	15844 KB	Output isn't correct
74	Correct	73 ms	15796 KB	Output is correct
75	Correct	77 ms	15904 KB	Output is correct
76	Correct	71 ms	15864 KB	Output is correct
77	Correct	75 ms	15832 KB	Output is correct
78	Correct	73 ms	15904 KB	Output is correct
79	Correct	62 ms	15912 KB	Output is correct
80	Correct	62 ms	15816 KB	Output is correct
81	Correct	70 ms	15884 KB	Output is correct
82	Correct	69 ms	15900 KB	Output is correct
83	Correct	92 ms	15780 KB	Output is correct
84	Correct	73 ms	15776 KB	Output is correct
85	Correct	82 ms	15780 KB	Output is correct
86	Correct	102 ms	15712 KB	Output is correct
87	Correct	83 ms	15780 KB	Output is correct
88	Correct	93 ms	15740 KB	Output is correct
89	Correct	87 ms	15752 KB	Output is correct
90	Correct	91 ms	15652 KB	Output is correct
91	Correct	93 ms	15712 KB	Output is correct
92	Correct	128 ms	15736 KB	Output is correct