Submission #1187916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187916		versesrev	Tracks in the Snow (BOI13_tracks)	C++20	2.19 / 100	1520 ms	45268 KiB

tracks

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cassert>

int main() {
  int h, w;
  std::cin >> h >> w;
  std::vector<std::string> grid(h);
  for (auto& s : grid) std::cin >> s;
  
  int ans = 0;
  int dr[4] = {1, 0, -1, 0};
  int dc[4] = {0, 1, 0, -1};
  std::priority_queue<std::tuple<int, int, int>> heap;
  std::vector<std::vector<bool>> vis(h, std::vector<bool>(w));
  heap.emplace(0, 0, 0), vis[0][0] = true;
  while (not heap.empty()) {
    auto [d, r, c] = heap.top();
    assert (ans == -d or ans-1 == -d);
    heap.pop();
    for (int k = 0; k < 4; ++k) {
      int nr = r + dr[k];
      int nc = c + dc[k];
      if (nr < 0 or h <= nr
      or nc < 0 or w <= nc
      or vis[nr][nc]
      or '.' == grid[nr][nc]) continue;
      int nd = d - (grid[nr][nc] != grid[r][c]);
      heap.emplace(nd, nr, nc);
      vis[nr][nc] = true;
      ans = std::max(ans, -d);
    }
  }
  std::cout << (ans + 1) << "\n";
}

• Subtask 1: 0 / 30
• Subtask 2: 2.1875 / 70