Submission #716291

#	Time	Username	Problem	Language	Result	Execution time	Memory
716291		nima_aryan	Tracks in the Snow (BOI13_tracks)	C++17	80.31 / 100	2115 ms	874124 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   int H, W;
   cin >> H >> W;
   vector grid(H, vector<char>(W));
   for (int i = 0; i < H; ++i) {
      for (int j = 0; j < W; ++j) {
         cin >> grid[i][j];
      }
   }
   auto id = [&](int i, int j) {
      return W * i + j;
   };
   auto di = [&](int i) {
      return make_pair(i / W, i % W);
   };
   auto get = [&](int node) {
      auto [i, j] = di(node);
      return grid[i][j];
   };
   const int N = H * W;
   vector<vector<int>> graph(N);
   auto add_edge = [&](int a, int b) {
      if (get(a) == '.' || get(b) == '.') {
         return;
      }
      graph[a].push_back(b);
      graph[b].push_back(a);
   };
   for (int i = 0; i < H; ++i) {
      for (int j = 0; j < W; ++j) {
         if (j + 1 < W) {
            add_edge(id(i, j), id(i, j + 1));
         }
         if (i + 1 < H) {
            add_edge(id(i, j), id(i + 1, j));
         }
      }
   }
   const int inf = (int) 1e9;
   vector<int> dist(N, inf);
   deque<int> dq;
   auto ad = [&](int node, int add, int extra = 0) {
      if (extra) {
         dq.push_back(node);
      }
      else {
         dq.push_front(node);
      }
      dist[node] = add + extra;
   };
   ad(0, 1);
   int ans = 1;
   while (!dq.empty()) {
      int node = dq.front();
      dq.pop_front();
      ans = max(ans, dist[node]);
      for (int neighbor : graph[node]) {
         if (dist[neighbor] < inf) {
            continue;
         }
         ad(neighbor, dist[node], get(node) != get(neighbor));
      }
   }
   cout << ans << '\n';
}

/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

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