oj.uz

Submission #637257

# Submission time Handle Problem Language Result Execution time Memory
637257 2022-09-01T07:55:29 Z iee Zoo (COCI19_zoo) C++17
110 / 110
 118 ms 6412 KB 
// iee
#include <bits/stdc++.h>

#define rep(i, a, b) for (auto i = (a); i <= (b); ++i)
#define per(i, a, b) for (auto i = (a); i >= (b); --i)
#define fi first
#define se second
using ll = long long;
using ull = unsigned long long;
using namespace std;
void work(int);

template <class T> void read(T &x) {
  x = 0; int f = 1, ch = getchar();
  while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
  while (isdigit(ch)) x = x * 10 + (ch - '0'), ch = getchar();
  x *= f;
}

int main() {
  int TT = 1; // cin >> TT;
  rep(CAS, 1, TT)
    work(CAS);
  return 0;
}
const int N = 1005;
int n, m;
char s[N][N];
int dis[N][N];
const int nxt[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
void work(int CASE) {
  scanf("%d%d", &n, &m);
  rep(i, 1, n) scanf("%s", s[i] + 1);
  priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> q;
  memset(dis, 0x3f, sizeof dis);
  q.emplace(dis[1][1] = 1, 1, 1);
  rep(i, 1, n) rep(j, 1, m) if (s[i][j] == '*') dis[i][j] = 0;
  while (!q.empty()) {
    int d, ux, uy;
    tie(d, ux, uy) = q.top();
    q.pop();
    if (dis[ux][uy] != d) continue;
   // cerr << d << ' ' << ux << ' ' << uy << '\n';
    rep(dir, 0, 3) {
      int vx = ux + nxt[dir][0];
      int vy = uy + nxt[dir][1];
      if (vx < 1 || vx > n || vy < 1 || vy > m) continue;
      int cost = d + (s[ux][uy] != s[vx][vy]);
      if (dis[vx][vy] > cost) {
        dis[vx][vy] = cost;
        q.emplace(cost, vx, vy);
      }
    }
  }
  int mx = 0;
  rep(i, 1, n) rep(j, 1, m)
    mx = max(mx, dis[i][j]);
  cout << mx;
}

Compilation message

zoo.cpp: In function 'void work(int)':
zoo.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
zoo.cpp:33:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   rep(i, 1, n) scanf("%s", s[i] + 1);
      |                ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 2 ms 4276 KB Output is correct
3 Correct 2 ms 4276 KB Output is correct
4 Correct 2 ms 4308 KB Output is correct
5 Correct 3 ms 4372 KB Output is correct
6 Correct 4 ms 4308 KB Output is correct
7 Correct 3 ms 4308 KB Output is correct
8 Correct 3 ms 4308 KB Output is correct
9 Correct 3 ms 4276 KB Output is correct
10 Correct 3 ms 4284 KB Output is correct
11 Correct 3 ms 4308 KB Output is correct
12 Correct 3 ms 4308 KB Output is correct
13 Correct 3 ms 4308 KB Output is correct
14 Correct 3 ms 4280 KB Output is correct
15 Correct 3 ms 4308 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 2 ms 4276 KB Output is correct
3 Correct 2 ms 4276 KB Output is correct
4 Correct 2 ms 4308 KB Output is correct
5 Correct 3 ms 4372 KB Output is correct
6 Correct 4 ms 4308 KB Output is correct
7 Correct 3 ms 4308 KB Output is correct
8 Correct 3 ms 4308 KB Output is correct
9 Correct 3 ms 4276 KB Output is correct
10 Correct 3 ms 4284 KB Output is correct
11 Correct 3 ms 4308 KB Output is correct
12 Correct 3 ms 4308 KB Output is correct
13 Correct 3 ms 4308 KB Output is correct
14 Correct 3 ms 4280 KB Output is correct
15 Correct 3 ms 4308 KB Output is correct
16 Correct 25 ms 6296 KB Output is correct
17 Correct 21 ms 6412 KB Output is correct
18 Correct 19 ms 6372 KB Output is correct
19 Correct 26 ms 6352 KB Output is correct
20 Correct 21 ms 6228 KB Output is correct
21 Correct 98 ms 6092 KB Output is correct
22 Correct 100 ms 6172 KB Output is correct
23 Correct 118 ms 6184 KB Output is correct
24 Correct 110 ms 6264 KB Output is correct
25 Correct 100 ms 6232 KB Output is correct
26 Correct 105 ms 6188 KB Output is correct
27 Correct 98 ms 6168 KB Output is correct
28 Correct 106 ms 6160 KB Output is correct
29 Correct 102 ms 6252 KB Output is correct
30 Correct 101 ms 6172 KB Output is correct