Submission #784840

#	Time	Username	Problem	Language	Result	Execution time	Memory
784840		jakobrs	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1871 ms	1048576 KiB

tracks

#include <iostream>
#include <set>
#include <vector>

using i32 = int32_t;

struct UnionFind {
  std::vector<i32> parent;

  explicit UnionFind(size_t sz) : parent(sz, -1) {}

  i32 find(i32 u) {
    if (parent[u] < 0)
      return u;
    else
      return parent[u] = find(parent[u]);
  }

  bool unite(i32 u, i32 v) {
    u = find(u);
    v = find(v);

    if (u == v) {
      return false;
    } else {
      if (-parent[u] < -parent[v])
        std::swap(u, v);

      parent[u] += parent[v];
      parent[v] = u;

      return false;
    }
  }
};

int main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);

  i32 h, w;
  std::cin >> h >> w;

  std::vector<std::string> grid(h);
  for (i32 i = 0; i < h; i++)
    std::cin >> grid[i];

  UnionFind dsu(h * w);

  i32 idx = 0;
  for (i32 r = 0; r < h; r++) {
    const auto &row = grid[r];
    for (i32 c = 0; c < w; c++, idx++) {
      if (c + 1 < w && grid[r][c] == grid[r][c + 1]) {
        dsu.unite(idx, idx + 1);
      }
      if (r + 1 < h && grid[r][c] == grid[r + 1][c]) {
        dsu.unite(idx, idx + w);
      }
    }
  }

  std::vector<std::set<i32>> adj(h * w);

  auto adge = [&](i32 u, i32 v) {
    adj[dsu.find(u)].insert(dsu.find(v));
    adj[dsu.find(v)].insert(dsu.find(u));
  };

  idx = 0;
  for (i32 r = 0; r < h; r++) {
    const auto &row = grid[r];
    for (i32 c = 0; c < w; c++, idx++) {
      if (row[c] == '.') continue;
      char op = row[c] == 'F' ? 'R' : 'F';

      if (c + 1 < w && grid[r][c + 1] == op) {
        adge(idx, idx + 1);
      }
      if (r + 1 < h && grid[r + 1][c] == op) {
        adge(idx, idx + w);
      }
    }
  }

  std::vector<i32> next;
  std::vector<i32> front { dsu.find(0) };
  std::vector<bool> visited(h * w, false);
  visited[0] = true;
  int t;
  for (t = 0; !front.empty(); t++) {
    for (int x : front) {
      for (int neighbour : adj[x]) {
        if (!visited[neighbour]) {
          visited[neighbour] = true;
          next.push_back(neighbour);
        }
      }
    }

    std::swap(next, front);
    next.clear();
  }

  std::cout << t;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:51:17: warning: unused variable 'row' [-Wunused-variable]
   51 |     const auto &row = grid[r];
      |                 ^~~

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