oj.uz

Submission #767737

# Submission time Handle Problem Language Result Execution time Memory
767737 2023-06-27T06:25:02 Z mgl_diamond Mecho (IOI09_mecho) C++14
53 / 100
 264 ms 4340 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using il = pair<ll, ll>;

#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second

void setIO(string name) {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  if (!name.empty()) {
    freopen((name + ".in").c_str(), "r", stdin);
    freopen((name + ".out").c_str(), "w", stdout);
  }
}

const int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
const int LIM = 1e9;
const int N = 808;

int n, s, vi[N][N];
ii st, en;
vector<ii> hives;
char a[N][N];

bool e(int i, int j) { return i >= 1 && i <= n && j >= 1 && j <= n; }

void propaganda(vector<ii> &lst, int xet, int dis) {
  queue<pair<ii, int>> bfs;
  for(auto x : lst) bfs.push({x, 0});
  lst.clear();
  
  while (!bfs.empty()) {
    auto at = bfs.front(); bfs.pop();
    int x = at.fi.fi, y = at.fi.se;

    if (vi[x][y] == 2 && xet == 1) {
      continue;
    }

    if (at.se == dis) {
      lst.emplace_back(at.fi);
      continue;
    }

    foru(d, 0, 3) {
      int nx = x+dx[d], ny = y+dy[d];
      if (!e(nx, ny) || a[nx][ny] == 'T') continue;
      if (xet == 2 && a[nx][ny] == 'D') continue;
      if (vi[nx][ny] != 0) {
        if (xet == 1) continue;
        if (vi[nx][ny] == 2) continue; 
      }
      vi[nx][ny] = xet;
      bfs.push({{nx, ny}, at.se+1});
    }
  }
}

void out() {
  foru(i, 1, n) {
    foru(j, 1, n) cout << vi[i][j] << " ";
    cout << "\n";
  }
  cout << "---------\n";
}

bool can(int eat_time) {
  memset(vi, 0, sizeof(vi));
  vector<ii> me, bees;
  me.emplace_back(st);
  bees = hives;
  propaganda(bees, 2, eat_time);
  while (!me.empty()) {
    propaganda(me, 1, s);
    propaganda(bees, 2, 1);
  }
  return vi[en.fi][en.se] == 1;
}

int main() {
  setIO("");

  cin >> n >> s;
  foru(i, 1, n)
    foru(j, 1, n) {
      cin >> a[i][j];
      if (a[i][j] == 'M') st = {i, j};
      else if (a[i][j] == 'D') en = {i, j};
      else if (a[i][j] == 'H') hives.emplace_back(i, j);
    }

  int ans = -1;
  for(int z=2*n; z>0; z>>=1) 
    while (ans+z < 2*n && can(ans+z))
      ans += z;
  
  cout << ans;
}

Compilation message

mecho.cpp: In function 'void setIO(std::string)':
mecho.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     freopen((name + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen((name + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
53.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 1 ms 2772 KB Output is correct
7 Correct 192 ms 3840 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 1 ms 2772 KB Output is correct
11 Correct 2 ms 2772 KB Output is correct
12 Incorrect 1 ms 2900 KB Output isn't correct
13 Correct 2 ms 2900 KB Output is correct
14 Correct 2 ms 2900 KB Output is correct
15 Incorrect 1 ms 2772 KB Output isn't correct
16 Incorrect 1 ms 2772 KB Output isn't correct
17 Incorrect 1 ms 2772 KB Output isn't correct
18 Incorrect 1 ms 2900 KB Output isn't correct
19 Incorrect 1 ms 2900 KB Output isn't correct
20 Incorrect 1 ms 2900 KB Output isn't correct
21 Incorrect 1 ms 2900 KB Output isn't correct
22 Incorrect 1 ms 2900 KB Output isn't correct
23 Incorrect 1 ms 2900 KB Output isn't correct
24 Incorrect 1 ms 2900 KB Output isn't correct
25 Incorrect 1 ms 2900 KB Output isn't correct
26 Incorrect 2 ms 2900 KB Output isn't correct
27 Incorrect 2 ms 2900 KB Output isn't correct
28 Incorrect 1 ms 2900 KB Output isn't correct
29 Incorrect 2 ms 2900 KB Output isn't correct
30 Incorrect 2 ms 2900 KB Output isn't correct
31 Incorrect 1 ms 2900 KB Output isn't correct
32 Incorrect 2 ms 2900 KB Output isn't correct
33 Incorrect 7 ms 3156 KB Output isn't correct
34 Incorrect 4 ms 3156 KB Output isn't correct
35 Correct 20 ms 3172 KB Output is correct
36 Incorrect 7 ms 3156 KB Output isn't correct
37 Incorrect 4 ms 3156 KB Output isn't correct
38 Correct 29 ms 3156 KB Output is correct
39 Incorrect 9 ms 3240 KB Output isn't correct
40 Incorrect 5 ms 3156 KB Output isn't correct
41 Correct 37 ms 3208 KB Output is correct
42 Incorrect 11 ms 3284 KB Output isn't correct
43 Incorrect 6 ms 3156 KB Output isn't correct
44 Correct 46 ms 3292 KB Output is correct
45 Incorrect 15 ms 3284 KB Output isn't correct
46 Incorrect 8 ms 3284 KB Output isn't correct
47 Correct 67 ms 3336 KB Output is correct
48 Incorrect 14 ms 3356 KB Output isn't correct
49 Incorrect 7 ms 3284 KB Output isn't correct
50 Correct 63 ms 3364 KB Output is correct
51 Incorrect 17 ms 3280 KB Output isn't correct
52 Incorrect 8 ms 3284 KB Output isn't correct
53 Correct 73 ms 3408 KB Output is correct
54 Incorrect 23 ms 3412 KB Output isn't correct
55 Incorrect 9 ms 3412 KB Output isn't correct
56 Correct 82 ms 3448 KB Output is correct
57 Incorrect 28 ms 3452 KB Output isn't correct
58 Incorrect 11 ms 3412 KB Output isn't correct
59 Correct 96 ms 3480 KB Output is correct
60 Incorrect 25 ms 3412 KB Output isn't correct
61 Incorrect 12 ms 3520 KB Output isn't correct
62 Correct 123 ms 3524 KB Output is correct
63 Correct 159 ms 3520 KB Output is correct
64 Correct 162 ms 3520 KB Output is correct
65 Correct 204 ms 3536 KB Output is correct
66 Correct 214 ms 3516 KB Output is correct
67 Correct 164 ms 3528 KB Output is correct
68 Correct 171 ms 3556 KB Output is correct
69 Correct 123 ms 3608 KB Output is correct
70 Correct 162 ms 3540 KB Output is correct
71 Correct 174 ms 3608 KB Output is correct
72 Correct 240 ms 3540 KB Output is correct
73 Correct 138 ms 4340 KB Output is correct
74 Correct 249 ms 3960 KB Output is correct
75 Correct 209 ms 3972 KB Output is correct
76 Correct 234 ms 3948 KB Output is correct
77 Correct 210 ms 4080 KB Output is correct
78 Correct 191 ms 4264 KB Output is correct
79 Correct 240 ms 3928 KB Output is correct
80 Correct 210 ms 3900 KB Output is correct
81 Correct 256 ms 3924 KB Output is correct
82 Correct 234 ms 3924 KB Output is correct
83 Correct 208 ms 4332 KB Output is correct
84 Correct 245 ms 3852 KB Output is correct
85 Correct 264 ms 3840 KB Output is correct
86 Correct 193 ms 4068 KB Output is correct
87 Correct 223 ms 3924 KB Output is correct
88 Correct 191 ms 4080 KB Output is correct
89 Correct 258 ms 3836 KB Output is correct
90 Correct 208 ms 4016 KB Output is correct
91 Correct 233 ms 3788 KB Output is correct
92 Correct 183 ms 4080 KB Output is correct