oj.uz

Submission #716292

# Submission time Handle Problem Language Result Execution time Memory
716292 2023-03-29T14:21:08 Z nima_aryan Tracks in the Snow (BOI13_tracks) C++14
84.6875 / 100
 2000 ms 978080 KB 
#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<string> grid(H);
   for (int i = 0; i < H; ++i) {
      cin >> grid[i];
   }
   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
 */

Compilation message

tracks.cpp: In lambda function:
tracks.cpp:27:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |       auto [i, j] = di(node);
      |            ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 14668 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 29 ms 9728 KB Output is correct
5 Correct 6 ms 3412 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 7 ms 3020 KB Output is correct
11 Correct 7 ms 2772 KB Output is correct
12 Correct 20 ms 5384 KB Output is correct
13 Correct 6 ms 3400 KB Output is correct
14 Correct 6 ms 3412 KB Output is correct
15 Correct 33 ms 13288 KB Output is correct
16 Correct 44 ms 14672 KB Output is correct
17 Correct 28 ms 10584 KB Output is correct
18 Correct 28 ms 9724 KB Output is correct

Subtask #2
54.6875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2260 KB Output is correct
2 Correct 152 ms 65332 KB Output is correct
3 Correct 878 ms 576604 KB Output is correct
4 Correct 240 ms 125324 KB Output is correct
5 Correct 640 ms 397752 KB Output is correct
6 Execution timed out 2083 ms 959656 KB Time limit exceeded
7 Correct 4 ms 2008 KB Output is correct
8 Correct 4 ms 2252 KB Output is correct
9 Correct 5 ms 2900 KB Output is correct
10 Correct 3 ms 1524 KB Output is correct
11 Correct 3 ms 2020 KB Output is correct
12 Correct 2 ms 1356 KB Output is correct
13 Correct 137 ms 65316 KB Output is correct
14 Correct 79 ms 38024 KB Output is correct
15 Correct 88 ms 37784 KB Output is correct
16 Correct 68 ms 29712 KB Output is correct
17 Correct 354 ms 167752 KB Output is correct
18 Correct 325 ms 148912 KB Output is correct
19 Correct 250 ms 125368 KB Output is correct
20 Correct 200 ms 126356 KB Output is correct
21 Correct 522 ms 337104 KB Output is correct
22 Correct 666 ms 397768 KB Output is correct
23 Correct 684 ms 322948 KB Output is correct
24 Correct 534 ms 353336 KB Output is correct
25 Correct 1757 ms 601544 KB Output is correct
26 Correct 1972 ms 758860 KB Output is correct
27 Execution timed out 2054 ms 978080 KB Time limit exceeded
28 Execution timed out 2102 ms 972304 KB Time limit exceeded
29 Execution timed out 2050 ms 972760 KB Time limit exceeded
30 Execution timed out 2068 ms 954108 KB Time limit exceeded
31 Execution timed out 2044 ms 619104 KB Time limit exceeded
32 Execution timed out 2102 ms 896112 KB Time limit exceeded