oj.uz

Submission #795035

# Submission time Handle Problem Language Result Execution time Memory
795035 2023-07-27T05:27:46 Z arush_agu Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1084 ms 98400 KB 
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#ifdef DEBUG
#include <time.h>
#endif

#define all(a) (a).begin(), (a).end()
#define rev(a) (a).rbegin(), (a).rend()
#define F first
#define S second
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x)                                                                 \
  {                                                                            \
    ++recur_depth;                                                             \
    auto x_ = x;                                                               \
    --recur_depth;                                                             \
    cerr << string(recur_depth, '\t') << "\e[91m" << __func__ << ":"           \
         << __LINE__ << "\t" << #x << " = " << x_ << "\e[39m" << endl;         \
  }
#else
#define dbg(x)
#endif

using namespace std;
using namespace __gnu_pbds;

typedef pair<int, int> ii;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> llll;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int>> vii;
typedef vector<vii> vvii;

typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pair<ll, ll>> vll;
typedef vector<vll> vvll;

typedef vector<bool> vb;

template <class type1>
using ordered_set = tree<type1, null_type, less<type1>, rb_tree_tag,
                         tree_order_statistics_node_update>;

template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<
                                    !is_same<T_container, string>::value,
                                    typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v) {
  os << '{';
  string sep;
  for (const T &x : v)
    os << sep << x, sep = ", ";
  return os << '}';
}

const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll INF = 1e9;
const ld EPS = 1e-9;

void solve() {
  int n, m;
  cin >> n >> m;
  vvi g(n, vi(m, -1));
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
      char c;
      cin >> c;
      if (c == 'R')
        g[i][j] = 0;
      if (c == 'F')
        g[i][j] = 1;
    }

  if (g[0][0])
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++)
        if (g[i][j] != -1)
          g[i][j] ^= 1;

  int cnt = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      if (g[i][j] != -1)
        cnt++;

  int cnt_seen = 0;
  queue<ii> q, nq;
  q.push({0, 0});
  vector<vb> vis(n, vb(m));
  int ans = 0;
  while (cnt_seen < cnt) {
    ans++;
    while (!q.empty()) {
      auto [r, c] = q.front();
      q.pop();

      if (vis[r][c])
        continue;
      vis[r][c] = 1;
      cnt_seen++;

      if (r > 0 && !vis[r - 1][c]) {
        if (g[r][c] == g[r - 1][c])
          q.push({r - 1, c});
        else if (g[r - 1][c] != -1)
          nq.push({r - 1, c});
      }

      if (r < n - 1 && !vis[r + 1][c]) {
        if (g[r][c] == g[r + 1][c])
          q.push({r + 1, c});
        else if (g[r + 1][c] != -1)
          nq.push({r + 1, c});
      }

      if (c > 0 && !vis[r][c - 1]) {
        if (g[r][c] == g[r][c - 1])
          q.push({r, c - 1});
        else if (g[r][c - 1] != -1)
          nq.push({r, c - 1});
      }

      if (c < m - 1 && !vis[r][c + 1]) {
        if (g[r][c] == g[r][c + 1])
          q.push({r, c + 1});
        else if (g[r][c + 1] != -1)
          nq.push({r, c + 1});
      }
    }

    swap(q, nq);
  }

  cout << ans << "\n";
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);

  clock_t start = clock();

  int test_cases = 1;
  // cin >> test_cases;

  while (test_cases--)
    solve();

#ifdef DEBUG
  cerr << fixed << setprecision(10)
       << "\nTime Taken: " << (double)(clock() - start) / CLOCKS_PER_SEC
       << "s\n";
#endif
  return 0;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:173:11: warning: unused variable 'start' [-Wunused-variable]
  173 |   clock_t start = clock();
      |           ^~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1648 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 8 ms 1356 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 6 ms 760 KB Output is correct
13 Correct 3 ms 724 KB Output is correct
14 Correct 3 ms 724 KB Output is correct
15 Correct 14 ms 1620 KB Output is correct
16 Correct 17 ms 1700 KB Output is correct
17 Correct 11 ms 1580 KB Output is correct
18 Correct 8 ms 1312 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 57 ms 8372 KB Output is correct
3 Correct 349 ms 80868 KB Output is correct
4 Correct 90 ms 19300 KB Output is correct
5 Correct 200 ms 45680 KB Output is correct
6 Correct 1084 ms 98388 KB Output is correct
7 Correct 2 ms 980 KB Output is correct
8 Correct 2 ms 980 KB Output is correct
9 Correct 3 ms 580 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 980 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 56 ms 8280 KB Output is correct
14 Correct 32 ms 4940 KB Output is correct
15 Correct 24 ms 5404 KB Output is correct
16 Correct 27 ms 3540 KB Output is correct
17 Correct 151 ms 20860 KB Output is correct
18 Correct 86 ms 20520 KB Output is correct
19 Correct 95 ms 19264 KB Output is correct
20 Correct 81 ms 17716 KB Output is correct
21 Correct 197 ms 47248 KB Output is correct
22 Correct 197 ms 45680 KB Output is correct
23 Correct 320 ms 39408 KB Output is correct
24 Correct 193 ms 46164 KB Output is correct
25 Correct 566 ms 80780 KB Output is correct
26 Correct 556 ms 62092 KB Output is correct
27 Correct 765 ms 84148 KB Output is correct
28 Correct 1068 ms 98400 KB Output is correct
29 Correct 1042 ms 94644 KB Output is correct
30 Correct 943 ms 92600 KB Output is correct
31 Correct 880 ms 52832 KB Output is correct
32 Correct 661 ms 82896 KB Output is correct