oj.uz

답안 #679577

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
679577 2023-01-08T15:00:09 Z peijar Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1152 ms 161696 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
  out << "[";
  for (int i = 0; i < (int)vec.size(); ++i) {
    out << vec[i];
    if (i + 1 < (int)vec.size())
      out << ", ";
  }
  return out << "]";
}
} // namespace std

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << H;
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

pair<int, int> DELTAS[] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbLig, nbCol;
  cin >> nbLig >> nbCol;

  vector<vector<int>> grid(nbLig, vector<int>(nbCol, -1));
  for (int lig = 0; lig < nbLig; ++lig)
    for (int col = 0; col < nbCol; ++col) {
      char c;
      cin >> c;
      if (c == 'F')
        grid[lig][col] = 0;
      else if (c == 'R')
        grid[lig][col] = 1;
    }
  array<queue<pair<int, int>>, 2> files;

  files[grid[0][0]].emplace(0, 0);

  int sol = 0;

  auto isSafe = [&](int lig, int col) {
    return lig >= 0 and col >= 0 and lig < nbLig and col < nbCol and
           grid[lig][col] >= 0;
  };

  while (true) {
    int curVal = files[0].empty() ? 1 : 0;
    if (files[curVal].empty())
      break;
    sol++;

    while (!files[curVal].empty()) {
      auto [lig, col] = files[curVal].front();
      files[curVal].pop();
      for (auto [dlig, dcol] : DELTAS) {
        int l = lig + dlig, c = col + dcol;
        if (!isSafe(l, c))
          continue;
        files[grid[l][c]].emplace(l, c);
        grid[l][c] = -1;
      }
    }
  }
  cout << sol << endl;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 2516 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 7 ms 1908 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 0 ms 316 KB Output is correct
7 Correct 1 ms 340 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 900 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 6 ms 1092 KB Output is correct
13 Correct 3 ms 980 KB Output is correct
14 Correct 3 ms 980 KB Output is correct
15 Correct 12 ms 2540 KB Output is correct
16 Correct 14 ms 2472 KB Output is correct
17 Correct 9 ms 2380 KB Output is correct
18 Correct 8 ms 1912 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 844 KB Output is correct
2 Correct 56 ms 14052 KB Output is correct
3 Correct 386 ms 141360 KB Output is correct
4 Correct 104 ms 33300 KB Output is correct
5 Correct 248 ms 79684 KB Output is correct
6 Correct 1152 ms 161696 KB Output is correct
7 Correct 2 ms 840 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 3 ms 840 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 2 ms 840 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 59 ms 14120 KB Output is correct
14 Correct 31 ms 8288 KB Output is correct
15 Correct 31 ms 9048 KB Output is correct
16 Correct 28 ms 5984 KB Output is correct
17 Correct 152 ms 36072 KB Output is correct
18 Correct 124 ms 35656 KB Output is correct
19 Correct 98 ms 33396 KB Output is correct
20 Correct 91 ms 30628 KB Output is correct
21 Correct 218 ms 82412 KB Output is correct
22 Correct 254 ms 79708 KB Output is correct
23 Correct 296 ms 68580 KB Output is correct
24 Correct 249 ms 80432 KB Output is correct
25 Correct 657 ms 141332 KB Output is correct
26 Correct 532 ms 108320 KB Output is correct
27 Correct 728 ms 144796 KB Output is correct
28 Correct 1132 ms 161632 KB Output is correct
29 Correct 1121 ms 158504 KB Output is correct
30 Correct 956 ms 154056 KB Output is correct
31 Correct 708 ms 91544 KB Output is correct
32 Correct 667 ms 142820 KB Output is correct