oj.uz

Submission #481412

# Submission time Handle Problem Language Result Execution time Memory
481412 2021-10-20T17:42:26 Z erlkonig Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 562 ms 135120 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define ar array
#define fi first
#define se second
#define ii pair <int, int>
#define vt vector
#define pb push_back
#define sz(x) (int)(x).size()
#define reset(a, x) memset(a, x, sizeof(a))
#define u128 __uint128_t

#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<=(b):i>=(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, (e)-1, 1)
#define F_OR2(i, e) F_OR(i, 0, (e)-1, 1)
#define F_OR3(i, b, e) F_OR(i, (b), (e), 1)
#define F_OR4(i, b, e, s) F_OR(i, (b), (e), (s))
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define fo(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define each(x, a) for (auto& x: a)
#define END cerr << "\n";

#define error(args...) { \
  string _s = #args; \
  replace(_s.begin(), _s.end(), ',', ' '); \
  stringstream _ss(_s); \
  istream_iterator <string> _it(_ss); \
  err(_it, args); \
}

void err(istream_iterator<string> it) {}

template<typename T, typename... Args> 
void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << "=" << a << ", ";
  err(++it, args...);
}

template<class T> void read(T& x) {
  cin >> x;
}

template<class H, class... T> void read(H& h, T&... t) {
  read(h);
  read(t...);
}

template<class A> void write(A x) {
  cout << x;
}

template<class H, class... T> void write(const H& h, const T&... t) { 
  write(h);
  write(t...);
}

void print() {
  write("\n");
}

template<class H, class... T> void print(const H& h, const T&... t) { 
  write(h);
  if(sizeof...(t))
    write(' ');
  print(t...);
}

#define file ""
//#define int ll

const long long INF = 2e18;
const int inf = 0x3c3c3c3c, N = 4e3;
int h, w, d[N][N];
deque <ii> dq;
string grid[N];

inline bool ok(int x, int y) {
  return (min(x, y) >= 0 && x < h && y < w && grid[x][y] != '.');
}

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};

void solve() {
  read(h, w);
  fo(h) read(grid[i]);
  reset(d, inf);
  d[0][0] = 1;
  dq.pb({0, 0});
  while (sz(dq)) {
    ii u = dq.front();
    dq.pop_front();
    fo(4) {
      int newx = u.fi+dx[i];
      int newy = u.se+dy[i];
      if (!ok(newx, newy)) continue;
      int cost = grid[u.fi][u.se] != grid[newx][newy];
      if (d[newx][newy] > d[u.fi][u.se]+cost) {
        d[newx][newy] = d[u.fi][u.se]+cost;
        if (cost) dq.pb({newx, newy});
        else dq.push_front({newx, newy});
      }
    }
  }
  int ans = 0;
  fo(x, h) fo(y, w) if (ok(x, y)) ans = max(ans, d[x][y]);
  write(ans);
}

int32_t main() {
  //freopen(file".out", "w", stdout); freopen(file".in", "r", stdin);
  cin.tie(0)->sync_with_stdio(0);
  int Case = 1;
  //read(Case);
  fo(ttest, 1, Case) {
    //write("Case ", ttest, ": ");
    solve();
  }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 63500 KB Output is correct
2 Correct 23 ms 62984 KB Output is correct
3 Correct 23 ms 62968 KB Output is correct
4 Correct 29 ms 63556 KB Output is correct
5 Correct 29 ms 63216 KB Output is correct
6 Correct 22 ms 63052 KB Output is correct
7 Correct 26 ms 63052 KB Output is correct
8 Correct 24 ms 62988 KB Output is correct
9 Correct 29 ms 62996 KB Output is correct
10 Correct 24 ms 63168 KB Output is correct
11 Correct 25 ms 63156 KB Output is correct
12 Correct 27 ms 63164 KB Output is correct
13 Correct 24 ms 63180 KB Output is correct
14 Correct 25 ms 63132 KB Output is correct
15 Correct 30 ms 63468 KB Output is correct
16 Correct 37 ms 63560 KB Output is correct
17 Correct 36 ms 63544 KB Output is correct
18 Correct 28 ms 63508 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 63048 KB Output is correct
2 Correct 51 ms 66124 KB Output is correct
3 Correct 175 ms 89196 KB Output is correct
4 Correct 69 ms 70592 KB Output is correct
5 Correct 144 ms 79556 KB Output is correct
6 Correct 551 ms 102876 KB Output is correct
7 Correct 22 ms 63052 KB Output is correct
8 Correct 24 ms 63044 KB Output is correct
9 Correct 23 ms 63088 KB Output is correct
10 Correct 22 ms 63124 KB Output is correct
11 Correct 24 ms 63052 KB Output is correct
12 Correct 24 ms 63000 KB Output is correct
13 Correct 51 ms 66124 KB Output is correct
14 Correct 41 ms 64888 KB Output is correct
15 Correct 40 ms 64972 KB Output is correct
16 Correct 39 ms 64332 KB Output is correct
17 Correct 97 ms 71328 KB Output is correct
18 Correct 88 ms 71080 KB Output is correct
19 Correct 68 ms 70656 KB Output is correct
20 Correct 61 ms 69964 KB Output is correct
21 Correct 114 ms 80300 KB Output is correct
22 Correct 147 ms 79556 KB Output is correct
23 Correct 169 ms 77128 KB Output is correct
24 Correct 114 ms 79772 KB Output is correct
25 Correct 343 ms 89156 KB Output is correct
26 Correct 317 ms 135120 KB Output is correct
27 Correct 445 ms 117820 KB Output is correct
28 Correct 562 ms 102896 KB Output is correct
29 Correct 519 ms 103776 KB Output is correct
30 Correct 469 ms 111620 KB Output is correct
31 Correct 392 ms 84592 KB Output is correct
32 Correct 366 ms 109288 KB Output is correct